{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count of Smaller Numbers After Self"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSmaller"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算右侧小于当前元素的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code><em> </em>，按要求返回一个新数组&nbsp;<code>counts</code><em> </em>。数组 <code>counts</code> 有该性质： <code>counts[i]</code> 的值是&nbsp; <code>nums[i]</code> 右侧小于&nbsp;<code>nums[i]</code> 的元素的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,2,6,1]\n",
    "<strong>输出：</strong><code>[2,1,1,0] \n",
    "<strong>解释：</strong></code>\n",
    "5 的右侧有 <strong>2 </strong>个更小的元素 (2 和 1)\n",
    "2 的右侧仅有 <strong>1 </strong>个更小的元素 (1)\n",
    "6 的右侧有 <strong>1 </strong>个更小的元素 (1)\n",
    "1 的右侧有 <strong>0 </strong>个更小的元素\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,-1]\n",
    "<strong>输出：</strong>[0,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-of-smaller-numbers-after-self](https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-of-smaller-numbers-after-self](https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,6,1]', '[-1]', '[-1,-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        lst = SortedList()\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            lst.add(nums[i])\n",
    "            nums[i] = lst.bisect_left(nums[i])\n",
    "        \n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        import bisect\n",
    "        n = len(nums)\n",
    "        ans = [None]*n\n",
    "        tmp = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            t = nums[i]\n",
    "            pos = bisect.bisect_left(tmp, t)\n",
    "            ans[i] = pos\n",
    "            tmp.insert(pos, t)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        # 新建一个排序的空列表\n",
    "        # 从右到左，添加原列表元素到该空列表中（二分查找）\n",
    "        # 添加位置即表示结果\n",
    "        n = len(nums)\n",
    "\n",
    "        sortNums = []\n",
    "        rs = [0] * n\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            index = bisect.bisect_left(sortNums, num)\n",
    "            sortNums.insert(index, num)\n",
    "            rs[i] = index\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        sortns = []\n",
    "        res = []\n",
    "        for num in reversed(nums):\n",
    "            idx = bisect.bisect_left(sortns, num)\n",
    "            res.append(idx)\n",
    "            sortns.insert(idx, num)\n",
    "            \n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        numlen = len(nums)\n",
    "        nums2 = nums.copy()\n",
    "        nums2.sort()\n",
    "        numdict = {}\n",
    "        for i in range(numlen):\n",
    "            if numdict.get(nums2[i]) == None:\n",
    "                numdict[nums2[i]] = i\n",
    "        tree = [0 for _ in range(numlen+1)]\n",
    "        ans = []\n",
    "        def add(index, val):\n",
    "            while index <= numlen:\n",
    "                tree[index] += 1\n",
    "                index += index & (-index)\n",
    "        def getsum(index):\n",
    "            res = 0\n",
    "            while index:\n",
    "                res += tree[index]\n",
    "                index -= index & (-index)\n",
    "            return res\n",
    "        def rangesum(left, right):\n",
    "            return getsum(right+1) - getsum(left)\n",
    "        for i in range(numlen-1, -1, -1):\n",
    "            now = numdict.get(nums[i])\n",
    "            ans.append(rangesum(0, now-1))\n",
    "            add(now+1, 1)\n",
    "        ans.reverse()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\r\n",
    "        def lowbit(x):\r\n",
    "            return x&(-x)\r\n",
    "        print(lowbit(0))\r\n",
    "        numset=set()\r\n",
    "        for num in nums:\r\n",
    "            numset.add(num)\r\n",
    "        numlist=list(numset)\r\n",
    "        numlist.sort()\r\n",
    "        def bs(num):\r\n",
    "            left=0\r\n",
    "            right=len(numlist)-1\r\n",
    "            while (left<=right):\r\n",
    "                mid=(left+right)//2\r\n",
    "                if numlist[mid]==num:\r\n",
    "                    return mid+1\r\n",
    "                elif numlist[mid]>num:\r\n",
    "                    right=mid-1\r\n",
    "                else:\r\n",
    "                    left=mid+1\r\n",
    "        tree=[0]*(len(numlist)+1)\r\n",
    "        def update(index):\r\n",
    "            i=index\r\n",
    "            while (i<len(numlist)):\r\n",
    "                tree[i]+=1\r\n",
    "                i+=lowbit(i)\r\n",
    "        def total(index):\r\n",
    "            t=0\r\n",
    "            i=index\r\n",
    "            while (i>0):\r\n",
    "                t+=tree[i]\r\n",
    "                i-=lowbit(i)\r\n",
    "            return t\r\n",
    "        res=[0]*len(nums)\r\n",
    "        for i in range(len(nums)-1,-1,-1):\r\n",
    "            index=bs(nums[i])\r\n",
    "            update(index)\r\n",
    "            res[i]=total(index-1)\r\n",
    "        return res\r\n",
    "            \r\n",
    "       \r\n",
    "       \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        class FenwickTree:\n",
    "            def __init__(self, n):\n",
    "                self.size = n\n",
    "                self.tree = [0 for _ in range(n + 1)]\n",
    "\n",
    "            def __lowbit(self, index):\n",
    "                return index & (-index)\n",
    "\n",
    "            # 单点更新：将 index 这个位置 + 1\n",
    "            def update(self, index, delta):\n",
    "                # 从下到上，最多到 size，可以等于 size\n",
    "                while index <= self.size:\n",
    "                    self.tree[index] += delta\n",
    "                    index += self.__lowbit(index)\n",
    "\n",
    "            # 区间查询：查询小于等于 index 的元素个数\n",
    "            # 查询的语义是\"前缀和\"\n",
    "            def query(self, index):\n",
    "                res = 0\n",
    "                # 从上到下，最少到 1，可以等于 1\n",
    "                while index > 0:\n",
    "                    res += self.tree[index]\n",
    "                    index -= self.__lowbit(index)\n",
    "                return res\n",
    "\n",
    "        # 特判\n",
    "        size = len(nums)\n",
    "        if size == 0:\n",
    "            return []\n",
    "        if size == 1:\n",
    "            return [0]\n",
    "\n",
    "        # 去重，方便离散化\n",
    "        s = list(set(nums))\n",
    "\n",
    "        s_len = len(s)\n",
    "\n",
    "        # 离散化，借助堆\n",
    "        import heapq\n",
    "        heapq.heapify(s)\n",
    "\n",
    "        rank_map = dict()\n",
    "        rank = 1\n",
    "        for _ in range(s_len):\n",
    "            num = heapq.heappop(s)\n",
    "            rank_map[num] = rank\n",
    "            rank += 1\n",
    "\n",
    "        fenwick_tree = FenwickTree(s_len)\n",
    "\n",
    "        # 从后向前填表\n",
    "        res = [None for _ in range(size)]\n",
    "        # 从后向前填表\n",
    "        for index in range(size - 1, -1, -1):\n",
    "            # 1、查询排名\n",
    "            rank = rank_map[nums[index]]\n",
    "            # 2、在树状数组排名的那个位置 + 1\n",
    "            fenwick_tree.update(rank, 1)\n",
    "            # 3、查询一下小于等于“当前排名 - 1”的元素有多少\n",
    "            res[index] = fenwick_tree.query(rank - 1)\n",
    "        return res\n",
    "\n",
    "# 作者：liweiwei1419\n",
    "# 链接：https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solutions/15614/shu-zhuang-shu-zu-by-liweiwei1419/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        h = set()\n",
    "        for i in nums:\n",
    "            h.add(i)\n",
    "        l = list(h)\n",
    "        l.sort()\n",
    "        for i in range(len(l)):\n",
    "            d[l[i]] = i+1\n",
    "        c = [0]*(len(l)+1)\n",
    "        def update(pos):\n",
    "            while pos < len(c):\n",
    "                c[pos] += 1\n",
    "                pos += (pos & -pos)\n",
    "        def query(pos):\n",
    "            ret = 0\n",
    "            while pos:\n",
    "                ret += c[pos]\n",
    "                pos -= pos & (-pos)\n",
    "            return ret\n",
    "        ret = []\n",
    "        # 计算当前比他小的数字的前缀和，逆序遍历\n",
    "        for j in range(len(nums)-1,-1,-1):\n",
    "            z = d[nums[j]]\n",
    "            he = query(z-1)\n",
    "            ret.append(he)\n",
    "            update(z)\n",
    "        return ret[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def mergesort(self,nums,sorttmp,index,index_tmp,res, l, r):\n",
    "        if l>=r:\n",
    "            return\n",
    "\n",
    "        mid = int((l+r)/2)\n",
    "        i = l\n",
    "        j = mid+1\n",
    "        sort_index = l\n",
    "\n",
    "        self.mergesort(nums,sorttmp,index,index_tmp,res,l,mid)\n",
    "        self.mergesort(nums,sorttmp,index,index_tmp,res,mid+1,r)\n",
    "\n",
    "        while(i<=mid and j<=r):\n",
    "            if nums[j] < nums[i]:\n",
    "                sorttmp[sort_index] = nums[j]\n",
    "                index_tmp[sort_index] = index[j]\n",
    "                j+=1\n",
    "                sort_index+=1\n",
    "            else:\n",
    "                sorttmp[sort_index] = nums[i]\n",
    "                index_tmp[sort_index] = index[i]\n",
    "                res[index[i]] += (j-mid-1)\n",
    "                i+=1\n",
    "                sort_index+=1\n",
    "            \n",
    "        while(i<=mid):\n",
    "            sorttmp[sort_index] = nums[i]\n",
    "            index_tmp[sort_index] = index[i]\n",
    "            res[index[i]] += (j-mid-1)\n",
    "            i+=1\n",
    "            sort_index+=1\n",
    "        \n",
    "        while(j<=r):\n",
    "            sorttmp[sort_index] = nums[j]\n",
    "            index_tmp[sort_index] = index[j]\n",
    "            j+=1\n",
    "            sort_index+=1\n",
    "        \n",
    "        for k in range(l,r+1):\n",
    "            nums[k] = sorttmp[k]\n",
    "            index[k] = index_tmp[k]\n",
    "\n",
    "\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        tmp = [0] * len(nums)\n",
    "        index = list(range(len(nums)))\n",
    "        index_tmp = [0] * len(nums)\n",
    "        res = [0] * len(nums)\n",
    "        self.mergesort(nums,tmp,index,index_tmp,res, 0, len(nums)-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def mergeSort(arr, indexes, counts, start, end):\n",
    "            if end - start <= 0:\n",
    "                return\n",
    "            mid = (start + end) // 2\n",
    "            mergeSort(arr, indexes, counts, start, mid)\n",
    "            mergeSort(arr, indexes, counts, mid + 1, end)\n",
    "\n",
    "            mergedArr, mergedIndexes = [], []\n",
    "            i, j = start, mid + 1\n",
    "            while i <= mid or j <= end:\n",
    "                if i <= mid and (j > end or arr[indexes[i]] <= arr[indexes[j]]):\n",
    "                    counts[indexes[i]] += j - (mid + 1)\n",
    "                    mergedArr.append(indexes[i])\n",
    "                    mergedIndexes.append(indexes[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    mergedArr.append(indexes[j])\n",
    "                    mergedIndexes.append(indexes[j])\n",
    "                    j += 1\n",
    "            for idx in range(len(mergedArr)):\n",
    "                indexes[start + idx] = mergedIndexes[idx]\n",
    "\n",
    "        n = len(nums)\n",
    "        indexes = list(range(n))\n",
    "        counts = [0] * n\n",
    "        mergeSort(nums, indexes, counts, 0, n - 1)\n",
    "        return counts\n",
    "\n",
    "# 测试示例\n",
    "# s = Solution()\n",
    "# print(s.countSmaller([5, 2, 6, 1]))  # 输出：[2, 1, 1, 0]\n",
    "# print(s.countSmaller([-1]))  # 输出：[0]\n",
    "# print(s.countSmaller([-1, -1]))  # 输出：[0, 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "class BitTree:\n",
    "    def __init__(self,n):\n",
    "        self.F = [0] * (n+1)\n",
    "        self.n = n + 1\n",
    "\n",
    "    def update(self,pos,v):\n",
    "        while pos < self.n:\n",
    "            self.F[pos] += v\n",
    "            pos += lowbit(pos)\n",
    "    \n",
    "    def query(self,pos):\n",
    "        if not pos:return 0\n",
    "        res = 0\n",
    "        while pos > 0:\n",
    "            res += self.F[pos]\n",
    "            pos -= lowbit(pos)\n",
    "        return res\n",
    "    \n",
    "    def qab(self,a,b): #[a,b]\n",
    "        return self.query(b) - self.query(a-1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        for idx,i in enumerate(nums):\n",
    "            G[i].append(idx)    \n",
    "        n = len(nums)\n",
    "        Res = [0] * n\n",
    "        Tr = BitTree(n)\n",
    "        for i in sorted(list(G.keys())):\n",
    "            for x in G[i]:\n",
    "                Res[x] = Tr.qab(x+1,n)\n",
    "            for x in G[i]:\n",
    "                Tr.update(x+1,1)\n",
    "        return Res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    index = []\n",
    "    temp = []\n",
    "    tempIndex = []\n",
    "    ans = []\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        # overtime !!!\n",
    "        # n = len(nums)\n",
    "        # counts = [0 for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     temp = 0\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if nums[i] > nums[j]:\n",
    "        #             temp += 1\n",
    "        #     counts[i] = temp\n",
    "        # return counts\n",
    "#  使用的是归并排序，其中使用一个新的list 用来存储右边小于左边的贡献值。\n",
    "        n = len(nums)\n",
    "        self.index = [i for i in range(n)]\n",
    "        self.temp = [0 for _ in range(n)]\n",
    "        self.tempIndex = [0 for _ in range(n)]\n",
    "        self.ans = [0 for _ in range(n)]\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        self.mergeSort(nums, l, r)\n",
    "        return [i for i in self.ans]\n",
    "\n",
    "    def mergeSort(self, nums, l, r):\n",
    "        if l >= r:\n",
    "            return\n",
    "        mid = (l + r) // 2\n",
    "        self.mergeSort(nums, l, mid)\n",
    "        self.mergeSort(nums, mid + 1, r)\n",
    "        self.merge(nums, l, mid, r)\n",
    "\n",
    "    def merge(self, nums, l, mid, r):\n",
    "        i = l\n",
    "        j = mid + 1\n",
    "        p = l\n",
    "        while i <= mid and j <= r:\n",
    "            if nums[i] <= nums[j]:\n",
    "                self.temp[p] = nums[i]\n",
    "                self.tempIndex[p] = self.index[i]\n",
    "                #  这个步骤的作用用来将当前 右侧已经知道的数据，小于左侧的个数，加到左边对应位置的 ans 上边。\n",
    "                self.ans[self.index[i]] += (j - mid - 1)\n",
    "                i += 1\n",
    "                p += 1\n",
    "            else:\n",
    "                self.temp[p] = nums[j]\n",
    "                self.tempIndex[p] = self.index[j]\n",
    "                j += 1\n",
    "                p += 1\n",
    "        while i <= mid:\n",
    "            self.temp[p] = nums[i]\n",
    "            self.tempIndex[p] = self.index[i]\n",
    "            self.ans[self.index[i]] += (j - mid - 1)\n",
    "            i += 1\n",
    "            p += 1\n",
    "        while j <= r:\n",
    "            self.temp[p] = nums[j]\n",
    "            self.tempIndex[p] = self.index[j]\n",
    "            j += 1\n",
    "            p += 1\n",
    "        for k in range(l, r+1):\n",
    "            self.index[k] = self.tempIndex[k]\n",
    "            nums[k] = self.temp[k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "计算右侧小于当前元素的个数\n",
    "给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质:  counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。\n",
    "\n",
    " \n",
    "\n",
    "示例 1: \n",
    "\n",
    "输入: nums = [5,2,6,1]\n",
    "输出: [2,1,1,0] \n",
    "解释: \n",
    "5 的右侧有 2 个更小的元素 (2 和 1)\n",
    "2 的右侧仅有 1 个更小的元素 (1)\n",
    "6 的右侧有 1 个更小的元素 (1)\n",
    "1 的右侧有 0 个更小的元素\n",
    "示例 2: \n",
    "\n",
    "输入: nums = [-1]\n",
    "输出: [0]\n",
    "示例 3: \n",
    "\n",
    "输入: nums = [-1,-1]\n",
    "输出: [0,0]\n",
    " \n",
    "\n",
    "提示: \n",
    "\n",
    "1 <= nums.length <= 105\n",
    "-104 <= nums[i] <= 104\n",
    "\n",
    "'''\n",
    "from typing import List\n",
    "\n",
    "'''\n",
    "树状数组(参考pdf)\n",
    "反正理解那个pdf之后背下\n",
    "lowBit,update,getSum函数就行了...\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def init(self,length):\n",
    "        # 树状数组用来求前缀和(相当于pdf中的c)\n",
    "        self.tree = [0] * (length+1)\n",
    "        # 原一维数组(相当于pdf中的a)\n",
    "        self.array = [0] * (length+1)\n",
    "\n",
    "    def lowBit(self, x):\n",
    "        return (x & (-x))\n",
    "\n",
    "    def update(self, pos, m):\n",
    "        # 树状数组的更新\n",
    "        # 原一维数组i的值增加m 会影响其他前缀和\n",
    "        while(pos < len(self.array)):\n",
    "            self.tree[pos] += m\n",
    "            pos += self.lowBit(pos)\n",
    "        return\n",
    "    \n",
    "    def getSum(self, pos):\n",
    "        # 求前缀和\n",
    "        ret = 0\n",
    "        while(pos > 0):\n",
    "            ret += self.tree[pos]\n",
    "            pos -= self.lowBit(pos)\n",
    "        return ret\n",
    "    \n",
    "    def discretization(self, nums:list):\n",
    "        # 离散化 即把原序列的值域映射到一个连续的整数区间，并保证它们的偏序关系不变\n",
    "        # 绝对大小不重要,重要的是相对大小,所以排序后用下标作为原值的映射\n",
    "        # 不能出现0 所以下标+1 0的话lowBit会无限循环\n",
    "        sorted_nums = sorted(set(nums))\n",
    "        discretizate_array = [(bisect.bisect_left(sorted_nums, n)+1) for n in (nums)]\n",
    "        return discretizate_array\n",
    "        \n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        # e.g. nums=[5,5,2,3,6]  ,discretizate_array=[3,3,1,2,4]\n",
    "        # 用哈希表记录每个数字出现个数 hash[num] = count 这个哈希表就是最终用来求前缀和的\n",
    "        # 从右向左遍历discretizate_array,先求前缀和,再更新哈希表,\n",
    "        # 比如遍历到右边第一个3的时候 计算其前缀和(hash_num[0],[1],[2],也就是getSum(pos=n-1)) => 1+1 =2 \n",
    "        # hash_num: 0 1 2 3 4 5 6 \n",
    "        # count:    0 1 1 0 1\n",
    "        # 详细步骤\n",
    "        # hash[4]+=1, 求前缀和getSum(pos=4-1)=0,更新数组树update(pos=4,m=1)\n",
    "        # hash[2]+=1, 求前缀和getSum(pos=2-1)=0,更新数组树update(pos=2,m=1)\n",
    "        # hash[1]+=1, 求前缀和getSum(pos=1-1)=0,更新数组树update(pos=1,m=1)\n",
    "        # hash[3]+=1, 求前缀和getSum(pos=3-1)-2,更新数组树update(pos=3,m=1)\n",
    "        # hash[3]+=1  求前缀和getSum(pos=3-1)=2,更新数组树update(pos=3,m=1)\n",
    "        self.init(len(nums))\n",
    "        tmpNums = self.discretization(nums)\n",
    "        result = []\n",
    "        for n in tmpNums[::-1]:\n",
    "            # self.array[n] += 1\n",
    "            preSum = self.getSum(pos=n-1)\n",
    "            result.append(preSum)\n",
    "            self.update(pos=n,m=1)\n",
    "        return result[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n = None\n",
    "        self.index = None\n",
    "        self.temp = None\n",
    "        self.temp_index = None\n",
    "        self.ans = None\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        self.n = len(nums)\n",
    "        self.index = [i for i in range(self.n)]\n",
    "        self.temp = [0 for _ in range(self.n)]\n",
    "        self.temp_index = [0 for _ in range(self.n)]\n",
    "        self.ans = [0 for _ in range(self.n)]\n",
    "        self.merge(nums, 0, self.n - 1)\n",
    "        return self.ans\n",
    "\n",
    "        \n",
    "    def merge(self, nums, i, j):\n",
    "        if i >= j:\n",
    "            return\n",
    "\n",
    "        mid = (i + j) >> 1\n",
    "        self.merge(nums, i ,mid)\n",
    "        self.merge(nums, mid+1, j)\n",
    "        self.merge_(nums, i, mid, j)\n",
    "\n",
    "    def merge_(self, nums, i, mid, j):\n",
    "        i_, j_ = i, mid + 1\n",
    "        p = i\n",
    "        while i_ <= mid and j_ <= j:\n",
    "            if nums[i_] <= nums[j_]:\n",
    "                self.temp[p] = nums[i_]\n",
    "                self.temp_index[p] = self.index[i_]\n",
    "                self.ans[self.index[i_]] += (j_ - mid - 1)\n",
    "                i_ += 1\n",
    "            else:\n",
    "                self.temp[p] = nums[j_]\n",
    "                self.temp_index[p] = self.index[j_]\n",
    "                j_ += 1\n",
    "            p += 1\n",
    "\n",
    "        while i_ <= mid:\n",
    "            self.temp[p] = nums[i_]\n",
    "            self.temp_index[p] = self.index[i_]\n",
    "            self.ans[self.index[i_]] += (j_ - mid - 1)\n",
    "            i_ += 1\n",
    "            p += 1\n",
    "            \n",
    "        while j_ <= j:\n",
    "            self.temp[p] = nums[j_]\n",
    "            self.temp_index[p] = self.index[j_]\n",
    "            j_ += 1\n",
    "            p += 1\n",
    "\n",
    "        self.index[i:j+1] = self.temp_index[i:j+1]\n",
    "        nums[i:j+1] = self.temp[i:j+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        idxList = []\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            idxList.append(i)\n",
    "            res.append(0)\n",
    "        mergeSort(nums, idxList, res)\n",
    "        return res\n",
    "\n",
    "\n",
    "def mergeSort(nums, idxList, res):\n",
    "    totalLen = len(nums)\n",
    "    nowLen = 1\n",
    "    while nowLen <= totalLen:\n",
    "        msort(nums, idxList, res, nowLen)\n",
    "        nowLen *= 2\n",
    "\n",
    "def msort(nums, idxList, res, nowLen):\n",
    "    arr = []\n",
    "    idxarr = []\n",
    "    start = 0\n",
    "    while start < len(nums):\n",
    "        arr1 = nums[start: start+nowLen]\n",
    "        arr2 = nums[start+nowLen: start + 2*nowLen]\n",
    "        idx1 = idxList[start: start+nowLen]\n",
    "        idx2 = idxList[start+nowLen: start + 2*nowLen]\n",
    "        start = start + 2*nowLen\n",
    "        r = merge(arr1, arr2, idx1, idx2, res)\n",
    "        arr += r[0]\n",
    "        idxarr += r[1]\n",
    "    for idx in range(len(arr)):\n",
    "        nums[idx] = arr[idx]\n",
    "        idxList[idx] = idxarr[idx]\n",
    "\n",
    "def merge(arr1, arr2, idx1, idx2, res):\n",
    "    i = 0\n",
    "    j = 0\n",
    "    arr = []\n",
    "    idxarr = []\n",
    "    while i < len(arr1) and j < len(arr2):\n",
    "        v1 = arr1[i]\n",
    "        v2 = arr2[j]\n",
    "        if v1 <= v2:\n",
    "            # 左侧排入的时候，右侧数组已经排入的个数，就是比左侧小的个数\n",
    "            res[idx1[i]] += j\n",
    "            arr.append(v1)\n",
    "            idxarr.append(idx1[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            # 右侧是已经排序了的，本身已经记录完了右侧有多少小的，就算左侧有更小的，也跟本题的统计无关了\n",
    "            arr.append(v2)\n",
    "            idxarr.append(idx2[j])\n",
    "            j += 1\n",
    "    while i < len(arr1):\n",
    "        res[idx1[i]] += j\n",
    "        arr.append(arr1[i])\n",
    "        idxarr.append(idx1[i])\n",
    "        i += 1\n",
    "    while j < len(arr2):\n",
    "        arr.append(arr2[j])\n",
    "        idxarr.append(idx2[j])\n",
    "        j += 1\n",
    "    return arr, idxarr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def merge(left,right,ans,left_index,right_index):\n",
    "            l,r = 0,0\n",
    "            \n",
    "            merge_list = []\n",
    "            merge_index = []\n",
    "            a = 0\n",
    "            while l < len(left) and r < len(right):\n",
    "                leftnum = left[l]\n",
    "                rightnum = right[r]\n",
    "                if leftnum <= rightnum:\n",
    "                    merge_list.append(leftnum)\n",
    "                    merge_index.append(left_index[l])\n",
    "                    ans[left_index[l]] += a\n",
    "                    l += 1\n",
    "                else:\n",
    "                    merge_list.append(rightnum)\n",
    "                    merge_index.append(right_index[r])\n",
    "                    r += 1\n",
    "                    a += 1\n",
    "                \n",
    "            while l < len(left):\n",
    "                merge_list.append(left[l])\n",
    "                merge_index.append(left_index[l])\n",
    "                ans[left_index[l]] += a\n",
    "                l += 1\n",
    "\n",
    "            while r < len(right):\n",
    "                merge_list.append(right[r])\n",
    "                merge_index.append(right_index[r])\n",
    "                r += 1\n",
    "            \n",
    "            return merge_list, ans, merge_index\n",
    "            \n",
    "            \n",
    "        \n",
    "        def mergesort(nums,ans,index):\n",
    "            if len(nums) == 1: \n",
    "                return nums,ans,[index[0]]\n",
    "            if len(nums) == 0:\n",
    "                return nums,ans,[]\n",
    "            \n",
    "            mid = len(nums) // 2\n",
    "            left,ans,left_index = mergesort(nums[:mid],ans,index[:mid])\n",
    "            right,ans,right_index = mergesort(nums[mid:],ans,index[mid:])\n",
    "            mergelist, ans, index = merge(left,right,ans,left_index,right_index)\n",
    "            # print(mergelist)\n",
    "            # print(ans)\n",
    "            return mergelist,ans,index\n",
    "        index = range(len(nums))\n",
    "        ans = [0] * len(nums)\n",
    "        mergelist, ans, index = mergesort(nums,ans,index)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        idx = sorted(list(set(nums)))\n",
    "        mp = {v: i + 1 for i, v in enumerate(idx)}\n",
    "        n = len(mp)\n",
    "        tot = [0] * (n * 4)\n",
    "        def add(o, l, r, i):\n",
    "            if l == r:\n",
    "                tot[o] += 1\n",
    "                return\n",
    "            m = l + r >> 1\n",
    "            if i <= m:\n",
    "                add(o * 2, l, m, i)\n",
    "            else:\n",
    "                add(o * 2 + 1, m + 1, r, i)\n",
    "            tot[o] = tot[o*2] + tot[o*2+1]\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                return tot[o]\n",
    "            s = 0\n",
    "            m = l + r >> 1\n",
    "            if L <= l:\n",
    "                s += query(o * 2, l, m, L, R)\n",
    "            if R > m:\n",
    "                s += query(o * 2 + 1, m + 1, r, L, R)\n",
    "            return s\n",
    "        ans = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            x = mp[nums[i]]\n",
    "            add(1, 1, n, x)\n",
    "            if x == 1: ans.append(0)\n",
    "            else: ans.append(query(1, 1, n, 1, x - 1))\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\r\n",
    "        self.ans = [0 for _ in nums]\r\n",
    "        self.merge_sort(list(enumerate(nums)))\r\n",
    "        return self.ans\r\n",
    "\r\n",
    "    def merge_sort(self, nums):\r\n",
    "        half = len(nums)//2\r\n",
    "        if half:\r\n",
    "            left, right = self.merge_sort(nums[:half]), self.merge_sort(nums[half:])\r\n",
    "            for i in range(len(nums)-1, -1, -1):\r\n",
    "                if not right or left and left[-1][1]>right[-1][1]: # 右边不存在 或者 左边大于右边\r\n",
    "                    self.ans[left[-1][0]] += len(right)\r\n",
    "                    nums[i] = left.pop()\r\n",
    "                else:\r\n",
    "                    nums[i] = right.pop()  \r\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        smaller = [0]*(len(nums))\n",
    "        self.merge_sort(list(enumerate(nums)), smaller)\n",
    "        return smaller\n",
    "\n",
    "    def merge_sort(self, nums, smaller):\n",
    "        if len(nums)<=1:\n",
    "            return \n",
    "\n",
    "        mid = len(nums)//2\n",
    "        left = nums[:mid]\n",
    "        right = nums[mid:]\n",
    "        self.merge_sort(left,smaller)\n",
    "        self.merge_sort(right,smaller)\n",
    "        self.merge(nums, left, right, smaller)\n",
    "\n",
    "    def merge(self, nums, left, right, smaller):\n",
    "        i=j=k=0\n",
    "        while i<len(left) and j<len(right):\n",
    "            if left[i][1]<=right[j][1]:\n",
    "                smaller[left[i][0]]+=j\n",
    "                nums[k]=left[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                nums[k]=right[j]\n",
    "                j+=1\n",
    "            k+=1\n",
    "        while i<len(left):\n",
    "            smaller[left[i][0]]+=j\n",
    "            nums[k]=left[i]\n",
    "            i+=1\n",
    "            k+=1\n",
    "\n",
    "        while j<len(right):\n",
    "            nums[k]=right[j]\n",
    "            j+=1\n",
    "            k+=1\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MergeSort:\n",
    "    def __init__(self, nums):\n",
    "        self.ans = [0] * len(nums)\n",
    "        self.nums = nums\n",
    "\n",
    "    def sort(self, low, high):\n",
    "        if low == high:\n",
    "            return self.nums[low:high+1]\n",
    "        mid = (low + high)//2\n",
    "\n",
    "        left = self.sort(low, mid)\n",
    "        right = self.sort(mid+1, high)\n",
    "\n",
    "        return self.merge(left, right)\n",
    "\n",
    "        \n",
    "    def merge(self, left, right):\n",
    "        res = []\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i][0] > right[j][0]:\n",
    "                res.append(right[j])\n",
    "                j += 1\n",
    "            else:\n",
    "                res.append(left[i])\n",
    "                self.ans[left[i][1]] += j\n",
    "                i += 1\n",
    "        if i == len(left):\n",
    "            res += right[j:]\n",
    "        else:\n",
    "            for k in range(i, len(left)):\n",
    "                self.ans[left[k][1]] += j\n",
    "            res += left[i:]\n",
    "        return res\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        nums = [(nums[i], i) for i in range(len(nums))]\n",
    "        ms = MergeSort(nums)\n",
    "        ms.sort(0, len(nums)-1)\n",
    "        return ms.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nn: int):\n",
    "        self.n = nn + 1\n",
    "        self.tree = [0] * (self.n)\n",
    "    def update(self, i: int, dis: int):\n",
    "        while i < self.n:\n",
    "            self.tree[i] += dis \n",
    "            i += i & -i\n",
    "    def ssum(self, i: int):\n",
    "        res = 0\n",
    "        while i:\n",
    "            res += self.tree[i] \n",
    "            i -= i & -i\n",
    "        return res\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        f = sorted(zip(nums, range(1, n + 1)))\n",
    "        mp = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            mp[f[i][0]] = i + 1 \n",
    "        for i, x in enumerate(nums):\n",
    "            nums[i] = mp[x]\n",
    "        print(nums)\n",
    "        root = BIT(n)\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans[i] = root.ssum(nums[i] - 1)\n",
    "            root.update(nums[i], 1)\n",
    "        \"\"\"\n",
    "        1 2\n",
    "        0 0 0\n",
    "        0 1 0\n",
    "        \"\"\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def merge_sort(nums, begin, end):\n",
    "            if begin >= end:\n",
    "                return\n",
    "            mid = (begin + end) // 2\n",
    "            merge_sort(nums, begin, mid)\n",
    "            merge_sort(nums, mid + 1, end)\n",
    "            left, right = begin, mid + 1\n",
    "            temp = []\n",
    "            while left <= mid and right <= end:\n",
    "                if nums[left][0] <= nums[right][0]:\n",
    "                    temp.append(nums[left])\n",
    "                    counts[nums[left][1]] += right - mid - 1\n",
    "                    left += 1\n",
    "                else:\n",
    "                    temp.append(nums[right])\n",
    "                    right += 1\n",
    "            while left <= mid:\n",
    "                temp.append(nums[left])\n",
    "                counts[nums[left][1]] += right - mid - 1\n",
    "                left += 1\n",
    "            while right <= end:\n",
    "                temp.append(nums[right])\n",
    "                right += 1\n",
    "            nums[begin: end + 1] = temp\n",
    "        lis = [[ele, i] for i, ele in enumerate(nums)]\n",
    "        counts = [0 for _ in range(len(nums))]\n",
    "        merge_sort(lis, 0, len(nums) - 1)\n",
    "        return counts\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        nums = [(s,i) for i,s in enumerate(nums)]\n",
    "        ans = [0]*len(nums)\n",
    "        #print(nums)\n",
    "        def dfs(nums):\n",
    "            n = len(nums)\n",
    "            if n <= 1:\n",
    "                return nums\n",
    "            mid = n // 2\n",
    "            left = dfs(nums[:mid])\n",
    "            right = dfs(nums[mid:])\n",
    "            #print(f'left {left}  right {right}')\n",
    "            l,ll,r,rr,i = 0,len(left),0,len(right),0\n",
    "            while l < ll or r < rr:\n",
    "                if r == rr or l < ll and left[l][0] <= right[r][0]:\n",
    "                    nums[i] = left[l]\n",
    "                    ans[left[l][1]] += r\n",
    "                    l += 1\n",
    "                else:\n",
    "                    nums[i] = right[r]\n",
    "                    r += 1\n",
    "                i += 1\n",
    "            return nums\n",
    "        dfs(nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        res = [0] * len(nums)\n",
    "        nums = [(num, idx) for idx, num in enumerate(nums)]\n",
    "        \n",
    "        def mergeSort(nums, low, high):\n",
    "            if low >= high:\n",
    "                return 0\n",
    "            mid = (low + high)//2 \n",
    "            mergeSort(nums, low, mid)\n",
    "            mergeSort(nums, mid+1, high)\n",
    "\n",
    "            temp = [] \n",
    "            left, right = low, mid+1 \n",
    "            while left <= mid and right <= high:\n",
    "                if nums[left][0] <= nums[right][0]:\n",
    "                    temp.append(nums[left])\n",
    "                    res[nums[left][1]] += right -(mid+1)\n",
    "                    left += 1 \n",
    "                else:\n",
    "                    temp.append(nums[right])\n",
    "                    right += 1 \n",
    "            while left <= mid:\n",
    "                temp.append(nums[left])\n",
    "                res[nums[left][1]] += right - (mid +1)\n",
    "                left += 1\n",
    "            while right <= high:\n",
    "                temp.append(nums[right])\n",
    "                right += 1\n",
    "            nums[low:high+1] = temp\n",
    "        mergeSort(nums, 0, len(nums)-1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def combine(left_arr, right_arr):\n",
    "            arr = []\n",
    "            left_index, right_index = 0, 0\n",
    "            while left_index < len(left_arr) and right_index < len(right_arr):\n",
    "                if left_arr[left_index] <= right_arr[right_index]:\n",
    "                    left_arr[left_index][2] += right_index\n",
    "                    arr.append(left_arr[left_index])\n",
    "                    left_index += 1\n",
    "                else:\n",
    "                    arr.append(right_arr[right_index])\n",
    "                    right_index += 1\n",
    "\n",
    "            while left_index < len(left_arr):\n",
    "                arr.append(left_arr[left_index])\n",
    "                left_arr[left_index][2] += right_index\n",
    "                left_index += 1\n",
    "\n",
    "            while right_index < len(right_arr):\n",
    "                arr.append(right_arr[right_index])\n",
    "                right_index += 1\n",
    "            return arr\n",
    "\n",
    "        def merge(nums):\n",
    "            n = len(nums)\n",
    "            if n < 2:\n",
    "                return nums\n",
    "            mid = n // 2\n",
    "            return combine(merge(nums[:mid]), merge(nums[mid:]))\n",
    "\n",
    "        nums = [[value, index, 0] for index, value in enumerate(nums)]\n",
    "        nums = merge(nums)\n",
    "        ans = [0 for _ in range(len(nums))]\n",
    "        for item in nums:\n",
    "            ans[item[1]] = item[2]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    给你一个整数数组 nums ，按要求返回一个新数组 counts 。\n",
    "    数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self.counts = []\n",
    "        self.tmps = []\n",
    "\n",
    "    def splitNum(self, nums, left, right):\n",
    "        if left >= right:\n",
    "            return\n",
    "        mid = left + (right - left) // 2\n",
    "        self.splitNum(nums, left, mid)\n",
    "        self.splitNum(nums, mid+1, right)\n",
    "        # print(nums)\n",
    "        self.mergeLis(nums, left, mid, right)\n",
    "        # print(nums)\n",
    "        return\n",
    "\n",
    "    def mergeLis(self, nums, left, mid, right):\n",
    "        lstart = left\n",
    "        rstart = mid + 1\n",
    "        \n",
    "        for idx in range(left, right+1):\n",
    "            self.tmps[idx] = nums[idx]\n",
    "        for idx in range(left, right+1):\n",
    "            if lstart == mid+1:\n",
    "                # 左侧已经遍历完了\n",
    "                nums[idx] = self.tmps[rstart]\n",
    "                rstart += 1\n",
    "            elif rstart == right+1:   # 注意right+1 ，边界是可以取等号\n",
    "                nums[idx] = self.tmps[lstart]\n",
    "                # self.count[self.tmp[pa].id] += pb - mid - 1\n",
    "                #                 pa += 1\n",
    "                self.counts[self.tmps[lstart][1]] += rstart - (mid + 1) # rstart=right, 所以不用加1\n",
    "                lstart += 1\n",
    "            # 左边大于右边的值， 那么counts[left] += count[right]\n",
    "            elif self.tmps[lstart][0] > self.tmps[rstart][0]:  # 注意此处是self.tmps, nums有重复值:\n",
    "                # 右边比较小，把右边的值插入，左边指针不动，右边下移，继续判断和左边的大小\n",
    "                nums[idx] = self.tmps[rstart]\n",
    "                rstart += 1\n",
    "            else:\n",
    "                nums[idx] = self.tmps[lstart]\n",
    "                # self.count[self.tmp[pa].id] += pb - mid - 1\n",
    "                #                 pa += 1\n",
    "                self.counts[self.tmps[lstart][1]] += rstart - (mid + 1)  # rstart=right, 所以不用加1\n",
    "                lstart += 1\n",
    "        # print(nums)\n",
    "        return\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        # 给你一个整数数组 nums ，按要求返回一个新数组 counts 。\n",
    "        # 数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。\n",
    "        self.counts = [0] * len(nums)\n",
    "        self.tmps = [[] for _ in range(len(nums))]\n",
    "        new_nums = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            new_nums.append([num, idx])\n",
    "        self.splitNum(new_nums, 0, len(nums)-1)\n",
    "        return self.counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        index = list(range(n))\n",
    "        res = [0] * n\n",
    "\n",
    "        def merge_sort(nums, low, high):\n",
    "            if low >= high:\n",
    "                return 0\n",
    "\n",
    "            mid = low + (high - low) // 2\n",
    "            merge_sort(nums, low, mid)\n",
    "            merge_sort(nums, mid + 1, high)\n",
    "\n",
    "            tmp = []\n",
    "            left, right = low, mid + 1\n",
    "            while left <= mid and right <= high:\n",
    "                if nums[index[left]] <= nums[index[right]]:\n",
    "                    tmp.append(index[left])\n",
    "                    res[index[left]] += right - (mid + 1)\n",
    "                    left += 1\n",
    "                else:\n",
    "                    tmp.append(index[right])\n",
    "                    right += 1\n",
    "\n",
    "            while left <= mid:\n",
    "                tmp.append(index[left])\n",
    "                res[index[left]] += right - (mid + 1)\n",
    "                left += 1\n",
    "\n",
    "            while right <= high:\n",
    "                tmp.append(index[right])\n",
    "                right += 1\n",
    "            index[low:high + 1] = tmp\n",
    "\n",
    "        merge_sort(nums, 0, n - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        indices = [i for i in range(n)]\n",
    "        res = [0] * n \n",
    "        tmp = [0] * n\n",
    "\n",
    "        def merge_and_count_smaller(left, right, nums):\n",
    "            if left >= right:\n",
    "                return\n",
    "            \n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            merge_and_count_smaller(left, mid, nums)\n",
    "            merge_and_count_smaller(mid+1, right, nums)\n",
    "\n",
    "            # if nums[indices[mid]] <= nums[indices[mid+1]]:\n",
    "            #    return # no need to sort across\n",
    "\n",
    "            for i in range(left, right+1):\n",
    "                tmp[i] = indices[i]\n",
    "            \n",
    "            i = left\n",
    "            j = mid + 1\n",
    "\n",
    "            for k in range(left, right+1):\n",
    "                if i > mid:\n",
    "                    indices[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j > right:\n",
    "                    indices[k] = tmp[i]\n",
    "                    i += 1\n",
    "                    res[indices[k]] += right - mid\n",
    "                elif nums[tmp[i]] <= nums[tmp[j]]:\n",
    "                    indices[k] = tmp[i]\n",
    "                    i += 1\n",
    "                    res[indices[k]] += (j - mid - 1)\n",
    "                else:\n",
    "                    indices[k] = tmp[j]\n",
    "                    j += 1\n",
    "        \n",
    "        merge_and_count_smaller(0, n-1, nums)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        self.res = [0 for _ in range(len(nums))]\n",
    "        temp = [[0,0] for _ in range(len(nums))]\n",
    "        numslist = [(i,v) for i,v in enumerate(nums)]\n",
    "        self.mergesort(numslist, 0, len(nums)-1, temp)\n",
    "        return self.res\n",
    "\n",
    "    def mergesort(self, numslist, start, end, temp):\n",
    "        if start==end or end == -1:\n",
    "            return\n",
    "        \n",
    "        mid = start+(end-start)//2\n",
    "        self.mergesort(numslist, start, mid, temp)\n",
    "        self.mergesort(numslist, mid+1, end, temp)\n",
    "\n",
    "        self.mergetogether(numslist, start, mid, end, temp)\n",
    "\n",
    "    def mergetogether(self, numslist, start, mid, end, temp):\n",
    "        i,j,k = start, mid+1, start\n",
    "        while i<=mid and j<=end:\n",
    "            if numslist[i][1]<=numslist[j][1]:\n",
    "                temp[k] = numslist[i]\n",
    "                self.res[numslist[i][0]] += j-mid-1\n",
    "                k+=1\n",
    "                i+=1\n",
    "            else:\n",
    "                temp[k] = numslist[j]\n",
    "                k+=1\n",
    "                j+=1\n",
    "        while i<=mid:\n",
    "            temp[k]=numslist[i]\n",
    "            self.res[numslist[i][0]] += j-mid-1\n",
    "            k+=1\n",
    "            i+=1\n",
    "        while j<=end:\n",
    "            temp[k]=numslist[j]\n",
    "            k+=1\n",
    "            j+=1\n",
    "        numslist[start:end+1] = temp[start:end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        g=len(nums)\n",
    "        for i in range(g):\n",
    "            nums[i]=[i,nums[i]]\n",
    "        z=[0 for _ in range(g)]\n",
    "        zz=z[:]\n",
    "        def ss(l,r):\n",
    "            if l==r-1:\n",
    "                return 0\n",
    "            m=(l+r)//2\n",
    "            mm=m\n",
    "            ll=l\n",
    "            ss(l,m)\n",
    "            ss(m,r)\n",
    "            hh=0\n",
    "            for t in range(l,r):\n",
    "                if l==mm:\n",
    "                    z[t]=nums[m]\n",
    "                    m+=1\n",
    "                elif m==r or nums[l][1]<=nums[m][1]:\n",
    "                    z[t]=nums[l]\n",
    "                    zz[nums[l][0]]+=hh\n",
    "                    l+=1\n",
    "                else:\n",
    "                    z[t]=nums[m]\n",
    "                    hh+=1\n",
    "                    m+=1\n",
    "            nums[ll:r]=z[ll:r]\n",
    "        ss(0,g)\n",
    "        return zz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        res=[0]*len(nums)\n",
    "        idx=[_ for _ in range(len(nums))]\n",
    "\n",
    "        def countSmaller(nums,l,r):\n",
    "            if l>=r: return\n",
    "            mid=(l+r)//2\n",
    "            countSmaller(nums,l,mid)\n",
    "            countSmaller(nums,mid+1,r)\n",
    "            merge(nums,l,mid,r)\n",
    "\n",
    "        def merge(nums,l,m,r):\n",
    "            arr=[]\n",
    "            i,j=l,m+1\n",
    "            while i<=m or j<=r:\n",
    "                if i>m or (j<=r and nums[idx[i]]<=nums[idx[j]]):\n",
    "                    arr.append(idx[j])\n",
    "                    j+=1\n",
    "                else:\n",
    "                    res[idx[i]]+=r-j+1\n",
    "                    arr.append(idx[i])\n",
    "                    i+=1\n",
    "\n",
    "            idx[l:r+1]=arr\n",
    "        \n",
    "        if len(nums)<2: return [0]\n",
    "        countSmaller(nums,0,len(nums)-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 经典题型 利用归并排序求解逆序数问题 可以延伸成本题\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        index = list(range(len(nums)))\n",
    "        res = [0] * len(nums)\n",
    "        def mergesort(low, high):\n",
    "            if low >= high:\n",
    "                return\n",
    "            mid = (low + high) // 2\n",
    "            # 分\n",
    "            mergesort(low, mid)\n",
    "            mergesort(mid + 1, high)\n",
    "            # 治 归并上面两个排序好的数组，同时统计右侧小于当前元素的个数\n",
    "            left, right = low, mid + 1\n",
    "            tmp = []\n",
    "            while left <= mid and right <= high:\n",
    "                if nums[index[left]] <= nums[index[right]]:\n",
    "                    tmp.append(index[left])\n",
    "                    res[index[left]] += right - (mid + 1)\n",
    "                    left += 1\n",
    "                else:\n",
    "                    tmp.append(index[right])\n",
    "                    right += 1\n",
    "            while left <= mid:\n",
    "                tmp.append(index[left])\n",
    "                res[index[left]] += right - (mid + 1)\n",
    "                left += 1\n",
    "            while right <= high:\n",
    "                tmp.append(index[right])\n",
    "                right += 1\n",
    "            index[low: high + 1] = tmp\n",
    "        mergesort(0, len(nums)-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        # 对nums做归并排序\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        nums=[[(nums[i],i)] for i in range(n)]\n",
    "        while len(nums)>1:\n",
    "            i=0\n",
    "            temp=[]\n",
    "            while i<len(nums)-1:\n",
    "                nums1=nums[i]\n",
    "                nums2=nums[i+1]\n",
    "                left=0\n",
    "                right=0\n",
    "                temp_nums=[]\n",
    "                while left<len(nums1):\n",
    "                    while right<len(nums2) and nums1[left][0]>nums2[right][0]:\n",
    "                        temp_nums.append(nums2[right])\n",
    "                        right+=1\n",
    "                    ans[nums1[left][1]]+=right\n",
    "                    temp_nums.append(nums1[left])\n",
    "                    left+=1\n",
    "                while right<len(nums2):\n",
    "                    temp_nums.append(nums2[right])\n",
    "                    right+=1\n",
    "                temp.append(temp_nums)\n",
    "                i+=2\n",
    "            if i==len(nums)-1:\n",
    "                temp.append(nums[i])\n",
    "            nums=temp\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pair:\n",
    "    def __init__(self,val,index):\n",
    "        self.val = val\n",
    "        self.index = index\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.tmp = []\n",
    "        self.count = []\n",
    "\n",
    "    def merge(self,datas,left,mid,right):\n",
    "        self.tmp=[]\n",
    "        i = left\n",
    "        j = mid+1\n",
    "        k = left\n",
    "        while i <=mid and j<=right:\n",
    "            if datas[i].val <= datas[j].val:\n",
    "                self.tmp.append(datas[i])\n",
    "                self.count[datas[i].index] +=j-mid-1\n",
    "                i+=1\n",
    "                \n",
    "            else:\n",
    "                self.tmp.append(datas[j])\n",
    "                j+=1\n",
    "        self.tmp+= datas[i:mid+1]\n",
    "        self.tmp+= datas[j:right+1]\n",
    "        for k in range(i,mid+1):\n",
    "             self.count[datas[k].index] += j-mid-1\n",
    "        \n",
    "    \n",
    "        datas[left:right+1] = self.tmp\n",
    "\n",
    "\n",
    "\n",
    "    def sort(self,datas,left,right):\n",
    "        if left==right:\n",
    "            return\n",
    "        mid = left+ ((right-left)>>1)\n",
    "        self.sort(datas,left,mid)\n",
    "        self.sort(datas,mid+1,right)\n",
    "        self.merge(datas,left,mid,right)\n",
    "\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        self.count = [0 for _ in range(len(nums))]\n",
    "        datas = [Pair(nums[i],i) for i in range(len(nums))]\n",
    "        self.sort(datas,0,len(nums)-1)\n",
    "        return self.count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]: #用归并排序来做\r\n",
    "        def merge_sort(arrs, left, right):\r\n",
    "            if right-left <= 1:\r\n",
    "                return\r\n",
    "            mid = (left+right)//2\r\n",
    "            merge_sort(arrs, left, mid)\r\n",
    "            merge_sort(arrs, mid, right)\r\n",
    "            merge(arrs, left, mid, right)\r\n",
    "\r\n",
    "        def merge(arrs, left, mid, right):\r\n",
    "            arrs2 = []\r\n",
    "            ll, rr = left, mid\r\n",
    "            while ll < mid or rr < right:\r\n",
    "                if rr == right or (ll < mid and rr < right and nums[arrs[ll][0]] <= nums[arrs[rr][0]]):\r\n",
    "                    arrs2.append([arrs[ll][0], arrs[ll][1]+rr-mid])\r\n",
    "                    ll += 1\r\n",
    "                else:\r\n",
    "                    arrs2.append([arrs[rr][0], arrs[rr][1]])\r\n",
    "                    rr += 1\r\n",
    "            arrs[left:right] = arrs2\r\n",
    "\r\n",
    "        n = len(nums)\r\n",
    "        res = []\r\n",
    "        for i in range(n):\r\n",
    "            res.append([i, 0])\r\n",
    "        merge_sort(res, 0, n)\r\n",
    "        counts = [0] * n\r\n",
    "        for i in range(n):\r\n",
    "            counts[res[i][0]] = res[i][1]\r\n",
    "        return counts\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pair():\n",
    "    def __init__(self, idx, val):\n",
    "        self.val = val\n",
    "        self.id = idx\n",
    "        \n",
    "class Solution:\n",
    "    def merge_sort(self, nums):\n",
    "        if len(nums) < 2:\n",
    "            return nums\n",
    "        mid = len(nums) // 2\n",
    "\n",
    "        left = self.merge_sort(nums[:mid])\n",
    "        right = self.merge_sort(nums[mid:])\n",
    "\n",
    "        return self.merge(left, right)\n",
    "    \n",
    "    def merge(self, left, right):\n",
    "        l, r = 0, 0\n",
    "        result = []\n",
    "\n",
    "        while l < len(left) and r < len(right):\n",
    "            if left[l].val <= right[r].val:\n",
    "                result.append(left[l])\n",
    "                self.count[left[l].id] += r\n",
    "                l += 1\n",
    "            else:\n",
    "                result.append(right[r])\n",
    "                # self.count[left[l].idx] += \n",
    "                r += 1\n",
    "            # print(self.count)\n",
    "\n",
    "        if l < len(left):\n",
    "            result += left[l:]\n",
    "            for i in range(l, len(left)):\n",
    "                self.count[left[i].id] += r\n",
    "\n",
    "        result += right[r:]\n",
    "        \n",
    "        return result\n",
    "    \n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        pairs = []\n",
    "        for i in range(len(nums)):\n",
    "            pairs.append(Pair(i, nums[i]))\n",
    "\n",
    "        self.count = [0] * len(nums)\n",
    "        \n",
    "        self.merge_sort(pairs)\n",
    "\n",
    "        return self.count\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "\n",
    "        self.temp = [0] * len(nums)\n",
    "        self.res = {i: 0 for i in range(len(nums))}\n",
    "\n",
    "        pair = [(nums[i], i) for i in range(len(nums))]\n",
    "        self.sort(pair, 0, len(pair)-1)\n",
    "\n",
    "        return [self.res[i] for i in range(len(nums))]\n",
    "\n",
    "    def sort(self, pair, low, high):\n",
    "        if low == high:\n",
    "            return\n",
    "\n",
    "        mid = low + (high - low) // 2\n",
    "        self.sort(pair, low, mid)\n",
    "        self.sort(pair, mid+1, high)\n",
    "        self.merge(pair, low, mid, high)\n",
    "\n",
    "    def merge(self, pair, low, mid, high):\n",
    "        for i in range(low, high+1):\n",
    "            self.temp[i] = pair[i]\n",
    "\n",
    "        i = low\n",
    "        j = mid + 1\n",
    "        for p in range(low, high+1):\n",
    "            if i > mid:\n",
    "                pair[p] = self.temp[j]\n",
    "                j += 1\n",
    "            elif j > high:\n",
    "                pair[p] = self.temp[i]\n",
    "                self.res[self.temp[i][1]] += j - mid - 1\n",
    "                i += 1\n",
    "            elif self.temp[i] <= self.temp[j]:\n",
    "                pair[p] = self.temp[i]\n",
    "                self.res[self.temp[i][1]] += j-mid-1\n",
    "                i += 1\n",
    "            else:\n",
    "                pair[p] = self.temp[j]\n",
    "                j += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    max_len =  10000\n",
    "    c = []\n",
    "    buckets = []\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        self.c = [0 for _ in range(len(nums) + 5)]\n",
    "        counts = [0 for _ in range(len(nums))]\n",
    "        nums = self.discretization(nums)\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            counts[i] = self.query(num-1)\n",
    "            self.updateC(num)\n",
    "        return counts\n",
    "\n",
    "    def updateC(self, pos):\n",
    "        while pos < len(self.c):\n",
    "            self.c[pos] += 1\n",
    "            pos += self.lowbit(pos)\n",
    "\n",
    "    def lowbit(self, x):\n",
    "        \"\"\"获取更新范围\"\"\"\n",
    "        return x & (-x)\n",
    "\n",
    "    def query(self, pos):\n",
    "        \"\"\"查询前缀和\"\"\"\n",
    "        val = 0\n",
    "        while pos > 0:\n",
    "            val += self.c[pos]\n",
    "            pos -= self.lowbit(pos)\n",
    "        return val\n",
    "\n",
    "    def getMappingList(self, nums):\n",
    "        \"\"\"列表去重排序\"\"\"\n",
    "        return list(sorted(set(nums)))\n",
    "\n",
    "    def discretization(self, nums):\n",
    "        \"\"\"将nums进行离散化变换\"\"\"\n",
    "        mapping = self.getMappingList(nums)\n",
    "        return [bisect_left(mapping, num) + 1 for num in nums]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countSmaller(self, nums):\n",
    "        deplicated_sorted_nums = np.sort(np.array(list(set(nums))))\n",
    "        nums_dict = {}\n",
    "        for idx, num in enumerate(deplicated_sorted_nums):\n",
    "            nums_dict[num] = idx\n",
    "        buckets = np.array([0] * len(deplicated_sorted_nums))\n",
    "        counts = []\n",
    "        for num in nums[::-1]:\n",
    "            buckets[nums_dict[num]] += 1\n",
    "            counts.append(np.sum(buckets[:nums_dict[num]]))\n",
    "\n",
    "        return [int(x) for x in counts[::-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pairs:\n",
    "    def __init__(self, idx, val):\n",
    "        self.idx = idx\n",
    "        self.val = val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        length = len(nums)\n",
    "        static_arr = [Pairs(0, 0)] * length\n",
    "        count = [0] * length\n",
    "        arr = [Pairs(i, nums[i]) for i in range(length)]\n",
    "\n",
    "        def _merge_sort(arr: List[Pairs], lo: int, hi: int) -> None:\n",
    "            if lo == hi:\n",
    "                return\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            _merge_sort(arr, lo, mid)\n",
    "            _merge_sort(arr, mid+1, hi)\n",
    "\n",
    "            _merge_arrays(arr, lo, mid, hi)\n",
    "\n",
    "        def _merge_arrays(arr: List[Pairs], lo: int, mid: int, hi: int):\n",
    "            for i in range(lo, hi + 1):\n",
    "                static_arr[i] = arr[i]\n",
    "            \n",
    "            i, j = lo, mid + 1\n",
    "            for p in range(lo, hi + 1):\n",
    "                if i == mid + 1:\n",
    "                    arr[p] = static_arr[j]\n",
    "                    j += 1\n",
    "                elif j == hi + 1:\n",
    "                    arr[p] = static_arr[i]\n",
    "                    i += 1\n",
    "                    count[arr[p].idx] += j - mid - 1\n",
    "                elif static_arr[i].val >  static_arr[j].val:\n",
    "                    arr[p] = static_arr[j]\n",
    "                    j += 1    \n",
    "                else:\n",
    "                    arr[p] = static_arr[i]\n",
    "                    i += 1\n",
    "                    count[arr[p].idx] += j - mid - 1\n",
    "\n",
    "        _merge_sort(arr, 0, length-1)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums) :\n",
    "        counts = [0]*len(nums)\n",
    "\n",
    "        def merge_sort(lo,hi):\n",
    "            if lo == hi: return [(nums[lo],lo)]\n",
    "            res = [[0,0]]*(hi-lo+1)\n",
    "            mi = (lo+hi)//2\n",
    "            list1 = merge_sort(lo,mi)\n",
    "            list2 = merge_sort(mi+1,hi)\n",
    "            i = j = 0\n",
    "            for k in range(len(res)):\n",
    "                if j == len(list2) or (i<len(list1) and list1[i][0]>list2[j][0]):\n",
    "                    res[k] = list1[i]\n",
    "                    counts[list1[i][1]]+=(len(list2)-j)\n",
    "                    i+=1\n",
    "                else:\n",
    "                    res[k] = list2[j]\n",
    "                    j+=1\n",
    "            return res\n",
    "        merge_sort(0,len(nums)-1)\n",
    "        return counts\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        num_idx = list(range(n))\n",
    "        res = [0]*n\n",
    "        def mergesort(l,r):\n",
    "            if l>=r:\n",
    "                return\n",
    "            mid = l + ((r-l)>>1)\n",
    "            mergesort(l,mid)\n",
    "            mergesort(mid+1,r)\n",
    "\n",
    "            i1,i2 = l,mid+1\n",
    "            helparr = [0]*(r-l+1)\n",
    "            helpidx = [0]*(r-l+1)\n",
    "            i = 0\n",
    "            while i1<=mid and i2<=r:\n",
    "                if nums[i1]>nums[i2]:\n",
    "                    res[num_idx[i1]] += r-i2+1\n",
    "                    helparr[i] = nums[i1]\n",
    "                    helpidx[i] = num_idx[i1]\n",
    "                    i1+=1\n",
    "                else:\n",
    "\n",
    "                    helparr[i] = nums[i2]\n",
    "                    helpidx[i] = num_idx[i2]\n",
    "                    i2+=1\n",
    "                i+=1\n",
    "            while i1<=mid:\n",
    "                helparr[i] = nums[i1]\n",
    "                helpidx[i] = num_idx[i1]\n",
    "                i1+=1\n",
    "                i+=1\n",
    "            while i2<=r:\n",
    "                helparr[i] = nums[i2]\n",
    "                helpidx[i] = num_idx[i2]\n",
    "                i2+=1\n",
    "                i+=1\n",
    "            for i in range(l,r+1):\n",
    "                nums[i] = helparr[i-l]\n",
    "                num_idx[i] = helpidx[i-l]\n",
    "        mergesort(0,n-1)\n",
    "        return res\n",
    "\n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n \n",
    "        index = [i for i in range(n)]\n",
    "        tmp = index[::]\n",
    "\n",
    "        def merge(nums, left, right, mid):\n",
    "            if left >= right:\n",
    "                return \n",
    "            for k in range(left, right+1):\n",
    "                tmp[k] = index[k]\n",
    "            i = left\n",
    "            j = mid + 1\n",
    "\n",
    "            for k in range(left, right+1):\n",
    "                if i > mid:\n",
    "                    index[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j > right:\n",
    "                    index[k] = tmp[i]\n",
    "                    i += 1\n",
    "                    res[index[k]] += j - (mid+1) \n",
    "                elif nums[tmp[i]] <= nums[tmp[j]]:\n",
    "                    index[k] = tmp[i]\n",
    "                    i += 1\n",
    "                    res[index[k]] += j - (mid+1)\n",
    "                else:\n",
    "                    index[k] = tmp[j]\n",
    "                    j += 1\n",
    "            \n",
    "\n",
    "        def mergeSort(nums, left, right):\n",
    "            if left >= right:\n",
    "                return \n",
    "            mid = (left + right) // 2\n",
    "            mergeSort(nums, left, mid)\n",
    "            mergeSort(nums, mid+1, right)\n",
    "            merge(nums, left, right, mid)\n",
    "        mergeSort(nums, 0, n-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def merge_sort(indexes):\n",
    "            if len(indexes) <= 1:\n",
    "                return indexes\n",
    "            \n",
    "            mid = len(indexes) // 2\n",
    "            left = merge_sort(indexes[:mid])\n",
    "            right = merge_sort(indexes[mid:])\n",
    "            \n",
    "            merged = []\n",
    "            left_count = 0\n",
    "            \n",
    "            i, j = 0, 0\n",
    "            while i < len(left) and j < len(right):\n",
    "                if nums[left[i]] <= nums[right[j]]:\n",
    "                    merged.append(left[i])\n",
    "                    result[left[i]] += left_count\n",
    "                    i += 1\n",
    "                else:\n",
    "                    merged.append(right[j])\n",
    "                    j += 1\n",
    "                    left_count += 1\n",
    "            \n",
    "            while i < len(left):\n",
    "                merged.append(left[i])\n",
    "                result[left[i]] += left_count\n",
    "                i += 1\n",
    "                \n",
    "            while j < len(right):\n",
    "                merged.append(right[j])\n",
    "                j += 1\n",
    "            \n",
    "            return merged\n",
    "        \n",
    "        result = [0] * len(nums)\n",
    "        indexes = list(range(len(nums)))\n",
    "        merge_sort(indexes)\n",
    "        \n",
    "        return result\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def mergesort(a):\n",
    "            d=len(a)\n",
    "            if d<=1: return a\n",
    "            left=mergesort(a[:d//2])\n",
    "            right=mergesort(a[d//2:])\n",
    "            ans=[]\n",
    "            i,j=0,0\n",
    "            m,n=len(left),len(right)\n",
    "            while i<m and j<n:\n",
    "                if nums[left[i]]<=nums[right[j]]:\n",
    "                    ans.append(left[i])\n",
    "                    counts[left[i]]+=j\n",
    "                    i+=1\n",
    "                    \n",
    "                else:\n",
    "                    ans.append(right[j])\n",
    "                    j+=1\n",
    "            for p in range(i,m):\n",
    "                ans.append(left[p])\n",
    "                counts[left[p]]+=j\n",
    "\n",
    "            for q in range(j,n):\n",
    "                ans.append(right[q])\n",
    "            return ans \n",
    "        \n",
    "        N=len(nums)\n",
    "        counts=[0]*N\n",
    "        mergesort(list(range(N)))\n",
    "        return counts\n",
    "\n",
    "            \n",
    "        # mi=min(nums)\n",
    "        # n=len(nums)\n",
    "        # for i in range(n):\n",
    "        #     nums[i]-=mi\n",
    "        \n",
    "        # mx=max(nums)\n",
    "        # a=[0]*(mx+2)\n",
    "        \n",
    "        # def lb(x):\n",
    "        #     return x&(-x)\n",
    "        # def add(i):\n",
    "        #     while i<len(a):\n",
    "        #         a[i]+=1\n",
    "        #         i+=lb(i)\n",
    "        #     return \n",
    "        # def query(i):\n",
    "        #     ans=0\n",
    "        #     while i:\n",
    "        #         ans+=a[i]\n",
    "        #         i-=lb(i)\n",
    "        #     return ans\n",
    "        # ans=[0]*n\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     ans[i]=query(nums[i])\n",
    "        #     add(nums[i]+1)\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        mn, mx = min(nums), max(nums) \n",
    "        d = [0] * ((mx - mn) * 4 + 5) \n",
    "        tg = [0] * ((mx - mn) * 4 + 5) \n",
    "        def putdown(s, t, p):\n",
    "            mid= (s + t) >> 1 \n",
    "            d[2*p] += tg[p] * (mid+1-s)\n",
    "            d[2*p+1] += tg[p] * (t - mid) \n",
    "            tg[2*p] += tg[p]\n",
    "            tg[2*p+1] += tg[p]\n",
    "            tg[p] = 0 \n",
    "\n",
    "        def query(s, t, p, l, r):\n",
    "            if s > r or l > t:\n",
    "                return 0 \n",
    "            if l<=s and t <=r:\n",
    "                return d[p]\n",
    "            mid = (s + t) >> 1\n",
    "            #print(s, t, p, l, r)\n",
    "            if tg[p]:\n",
    "                putdown(s, t, p) \n",
    "            tot = 0\n",
    "            if l <= mid:\n",
    "                tot += query(s,mid,2*p,l,r)\n",
    "            if r >= mid+1:\n",
    "                tot += query(mid+1,t, 2*p+1,l,r)\n",
    "            return tot \n",
    "        def update(s, t, p, l, r, v):\n",
    "            if s > r or l > t:\n",
    "                return \n",
    "            #print('*', s, t, p, l, r)\n",
    "            if l <= s and t <= r:\n",
    "                d[p] += v * (t - s + 1) \n",
    "                tg[p] += v \n",
    "                return \n",
    "            mid = (s + t) >> 1\n",
    "            if tg[p]:\n",
    "                putdown(s, t, p)\n",
    "            if l <= mid:\n",
    "                update(s, mid, 2 * p, l, r, v) \n",
    "            if r >= mid+1:\n",
    "                update(mid+1, t, 2 * p+1, l, r, v) \n",
    "            d[p] = d[2*p] + d[2*p+1] \n",
    "        n = len(nums) \n",
    "        ans = [0] * n \n",
    "        for i in range(n-1, -1,-1):\n",
    "            if nums[i] <= mn:\n",
    "                ans[i] = 0 \n",
    "            else:\n",
    "                tot = query(0, mx-mn, 1, 0, nums[i]-mn-1)\n",
    "                ans[i] = tot \n",
    "            update(0, mx-mn, 1, nums[i]-mn, nums[i]-mn, 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        def mergeSort(low, high):\n",
    "            if low >= high: return 0\n",
    "            mid = low + high >> 1\n",
    "            mergeSort(low, mid)    \n",
    "            mergeSort(mid + 1, high)        \n",
    "            tmp = []  \n",
    "            i, j = low, mid + 1\n",
    "            while i <= mid and j <= high:\n",
    "                if nums[index[i]] <= nums[index[j]]:\n",
    "                    tmp.append(index[i])\n",
    "                    res[index[i]] += j - (mid + 1) \n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp.append(index[j])\n",
    "                    j += 1\n",
    "            \n",
    "    \n",
    "            while i <= mid:\n",
    "                tmp.append(index[i])\n",
    "                res[index[i]] += j - (mid + 1)      # 记录逆序对数目\n",
    "                i += 1\n",
    "\n",
    "            while j <= high:\n",
    "                tmp.append(index[j])\n",
    "                j += 1\n",
    "            \n",
    "            index[low:high+1] = tmp\n",
    "\n",
    "\n",
    "        '''主程序'''\n",
    "        n = len(nums)\n",
    "        res = [0] * n           \n",
    "        index = list(range(n))     \n",
    "        mergeSort(0, n-1) \n",
    "        return res\n",
    "\n",
    "        res = []\n",
    "        sl = SortedList()\n",
    "        for x in reversed(nums):        \n",
    "            j = sl.bisect_left(x) \n",
    "            res.append(j)               \n",
    "            sl.add(x)        \n",
    "        \n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        new_arr = []\n",
    "        for i in range(len(nums)):\n",
    "            new_arr.append([nums[i], i])\n",
    "        res = [0] * len(nums)\n",
    "        def merge(left, right):\n",
    "            nonlocal res\n",
    "            i, j = 0, 0\n",
    "            merged = []\n",
    "            while i < len(left) and j < len(right):\n",
    "                if left[i][0] <= right[j][0]:\n",
    "                    res[left[i][1]] += j\n",
    "                    merged.append([left[i][0], left[i][1]])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    merged.append([right[j][0], right[j][1]])\n",
    "                    j += 1\n",
    "            while i < len(left):\n",
    "                res[left[i][1]] += j\n",
    "                merged.append([left[i][0], left[i][1]])\n",
    "                i += 1\n",
    "            while j < len(right):\n",
    "                merged.append([right[j][0], right[j][1]])\n",
    "                j += 1\n",
    "            return merged\n",
    "\n",
    "        def merge_f(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return arr\n",
    "            mid = len(arr) // 2\n",
    "            left = merge_f(arr[:mid])\n",
    "            right = merge_f(arr[mid:])\n",
    "            new_arr = merge(left, right)\n",
    "            return new_arr\n",
    "        merge_f(new_arr)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n   # 存储结果\n",
    "        idx = list(range(n)) # 建立索引数组\n",
    "    \n",
    "        def merge_sort(left: int, right: int):\n",
    "            # 归并排序\n",
    "            if left >= right:\n",
    "                return\n",
    "            mid = (left + right) // 2\n",
    "            merge_sort(left, mid)\n",
    "            merge_sort(mid + 1, right)\n",
    "            i, j = left, mid + 1\n",
    "            temp = []\n",
    "            while i <= mid and j <= right:\n",
    "                # 右边比左边小，统计逆序对的个数\n",
    "                if nums[idx[i]] > nums[idx[j]]:\n",
    "                    temp.append(idx[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    res[idx[i]] += j - (mid + 1)\n",
    "                    temp.append(idx[i])\n",
    "                    i += 1\n",
    "\n",
    "            while i <= mid:\n",
    "                temp.append(idx[i])\n",
    "                res[idx[i]] += right - mid\n",
    "                i += 1\n",
    "\n",
    "            while j <= right:\n",
    "                temp.append(idx[j])\n",
    "                j += 1\n",
    "            idx[left:right+1] = temp\n",
    "\n",
    "        merge_sort(0, n - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n   # 存储结果\n",
    "        idx = list(range(n)) # 建立索引数组\n",
    "    \n",
    "        def merge_sort(left: int, right: int):\n",
    "            # 归并排序\n",
    "            if left >= right:\n",
    "                return\n",
    "            mid = (left + right) // 2\n",
    "            merge_sort(left, mid)\n",
    "            merge_sort(mid + 1, right)\n",
    "            i, j = left, mid + 1\n",
    "            temp = []\n",
    "            while i <= mid and j <= right:\n",
    "                # 右边比左边小，统计逆序对的个数\n",
    "                if nums[idx[i]] > nums[idx[j]]:\n",
    "                    temp.append(idx[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    res[idx[i]] += j - (mid + 1)\n",
    "                    temp.append(idx[i])\n",
    "                    i += 1\n",
    "\n",
    "            while i <= mid:\n",
    "                temp.append(idx[i])\n",
    "                res[idx[i]] += right - mid\n",
    "                i += 1\n",
    "\n",
    "            while j <= right:\n",
    "                temp.append(idx[j])\n",
    "                j += 1\n",
    "            idx[left:right+1] = temp\n",
    "\n",
    "        merge_sort(0, n - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        self.count = [0] * len(nums)\n",
    "        self.nums_idx = list(range(len(nums)))\n",
    "        def merge_sort(start, end):\n",
    "            if start == end:\n",
    "                return \n",
    "            mid = (start + end) // 2\n",
    "            merge_sort(start, mid)\n",
    "            merge_sort(mid + 1, end)\n",
    "            left, right = start, mid+1\n",
    "            res = []\n",
    "            while left <= mid or right <= end:\n",
    "                if left > mid or (right <= end and nums[self.nums_idx[left]] > nums[self.nums_idx[right]]):\n",
    "                    res.append(self.nums_idx[right])\n",
    "                    right += 1\n",
    "                else:\n",
    "                    self.count[self.nums_idx[left]] += right - mid - 1\n",
    "                    res.append(self.nums_idx[left])\n",
    "                    left += 1\n",
    "            self.nums_idx[start: end + 1] = res\n",
    "        merge_sort(0, len(nums) - 1)\n",
    "        return self.count\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pair:\n",
    "    def __init__(self, id, val):\n",
    "        self.val = val\n",
    "        self.id = id\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.temp = []\n",
    "        self.count = []\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        self.temp = [Pair(0, 0) for _ in range(len(nums))]\n",
    "        self.count = [0 for _ in range(len(nums))]\n",
    "        arr = [Pair(i, nums[i]) for i in range(len(nums))]\n",
    "        self.sort(arr, 0, len(nums) - 1)\n",
    "        return self.count\n",
    "\n",
    "    def sort(self, nums, low, high):\n",
    "        if low == high:\n",
    "            return\n",
    "        mid = low + (high - low) // 2\n",
    "\n",
    "        self.sort(nums, low, mid)\n",
    "        self.sort(nums, mid + 1, high)\n",
    "\n",
    "        self.merge(nums, low, mid, high)\n",
    "\n",
    "    def merge(self, nums, low, mid, high):\n",
    "        for i in range(low, high + 1):\n",
    "            self.temp[i] = nums[i]\n",
    "        i = low\n",
    "        j = mid + 1\n",
    "        for p in range(low, high + 1):\n",
    "            if i == mid + 1:\n",
    "                nums[p] = self.temp[j]\n",
    "                j += 1\n",
    "            elif j == high + 1:\n",
    "                nums[p] = self.temp[i]\n",
    "                i += 1\n",
    "                self.count[nums[p].id] += j-mid-1\n",
    "            elif self.temp[i].val > self.temp[j].val:\n",
    "                nums[p] = self.temp[j]\n",
    "                j += 1\n",
    "            elif self.temp[i].val <= self.temp[j].val:\n",
    "                nums[p] = self.temp[i]\n",
    "                i += 1\n",
    "                self.count[nums[p].id] += j-mid-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        class Pair:\n",
    "            def __init__(self, val, idx):\n",
    "                self.val = val\n",
    "                self.idx = idx\n",
    "\n",
    "        # 归并排序 \n",
    "        def sort(arr, lo, hi):\n",
    "            if lo == hi:\n",
    "                return \n",
    "            mid = lo + (hi-lo)//2\n",
    "            sort(arr, lo, mid)\n",
    "            sort(arr, mid+1, hi)\n",
    "            merge(arr, lo, mid, hi)\n",
    "        \n",
    "        # 合并两个有序数组 arr[lo..mid] 和 arr[mid+1..hi]\n",
    "        def merge(arr, lo, mid, hi):\n",
    "            # 将两个有序数组复制到 辅助数组上\n",
    "            for i in range(lo, hi+1):\n",
    "                temp[i] = arr[i]\n",
    "            \n",
    "            i, j = lo, mid+1\n",
    "            for p in range(lo, hi+1):\n",
    "                if i == mid+1:\n",
    "                    # 左半边数组已全部被合并\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                elif j == hi+1:\n",
    "                    # 右半边数组已全部被合并\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "                    # 更新count数组\n",
    "                    count[arr[p].idx] += hi-mid\n",
    "                elif temp[i].val > temp[j].val:\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "                    # 更新count数组\n",
    "                    count[arr[p].idx] += j-mid-1\n",
    "        \n",
    "        # 归并排序要用到的辅助数组\n",
    "        temp = [Pair(0, 0) for _ in range(len(nums))]\n",
    "        # 记录每个元素后面比自己小的元素个数\n",
    "        count = [0 for _ in range(len(nums))]\n",
    "\n",
    "        arr = [Pair(nums[idx], idx) for idx in range(len(nums))]\n",
    "        # 执行归并排序\n",
    "        sort(arr, 0, len(nums)-1)\n",
    "\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        class Pair:\n",
    "            def __init__(self, val, id):\n",
    "                self.val = val\n",
    "                self.id = id\n",
    "        n = len(nums)\n",
    "        pair = [Pair(nums[i], i) for i in range(n)]\n",
    "        res = [0 for _ in range(n)]\n",
    "        tmp = [Pair(0,0) for _ in range(n)] #只改变pair, tmp不改\n",
    "        \n",
    "\n",
    "        def postorder(pair, low, high):\n",
    "            if low == high:\n",
    "                return\n",
    "            mid = low + (high - low) // 2\n",
    "            postorder(pair, low, mid)\n",
    "            postorder(pair, mid + 1, high)\n",
    "            merge(pair, low, mid, high)\n",
    "    \n",
    "        def merge(pair, low, mid, high):\n",
    "            for i in range(low, high + 1):\n",
    "                tmp[i] = pair[i]\n",
    "            i, j = low, mid + 1\n",
    "            for k in range(low, high + 1):\n",
    "                if i == mid + 1:\n",
    "                    pair[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j == high + 1:\n",
    "                    pair[k] = tmp[i]\n",
    "                    i += 1\n",
    "                    res[pair[k].id] += j - mid - 1\n",
    "                elif tmp[i].val <= tmp[j].val:\n",
    "                    pair[k] = tmp[i]\n",
    "                    i += 1\n",
    "                    res[pair[k].id] += j - mid - 1\n",
    "                else:\n",
    "                    pair[k] = tmp[j]\n",
    "                    j += 1\n",
    "            \n",
    "        postorder(pair, 0, n - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pair:\n",
    "    def __init__(self, val: int, id: int):\n",
    "        # 记录数组的元素值\n",
    "        self.val = val\n",
    "        # 记录元素在数组中的原始索引\n",
    "        self.id = id\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        temp =  [Pair(0,0) for _ in range(len(nums))]\n",
    "        count = [0]*len(nums)\n",
    "        def merge(arr, start, mid, end):\n",
    "            \n",
    "            for i in range(start, end+1):\n",
    "                temp[i] = arr[i]\n",
    "            \n",
    "            left, right = start, mid+1\n",
    "            for k in range(start, end+1):\n",
    "                if left > mid:\n",
    "                    nums[k] = temp[right]\n",
    "                    right+=1\n",
    "                    \n",
    "                elif right > end:\n",
    "                    nums[k] = temp[left]\n",
    "                    left+=1\n",
    "                    count[nums[k].id] += (right-mid-1)\n",
    "                elif temp[left].val > temp[right].val:\n",
    "                    nums[k] = temp[right]\n",
    "                    right +=1\n",
    "                else:\n",
    "                    nums[k] = temp[left]\n",
    "                    left += 1\n",
    "                    count[nums[k].id] += (right-mid-1)\n",
    "                    \n",
    "\n",
    "        \n",
    "        def sort(arr, start, end):\n",
    "            \n",
    "            if start >= end:\n",
    "                return \n",
    "            \n",
    "            mid = start + (end - start)//2\n",
    "            sort(arr, start, mid)\n",
    "            sort(arr, mid+1, end)\n",
    "            merge(arr, start, mid, end)\n",
    "        nums = [Pair(nums[i], i) for i in range(len(nums))]\n",
    "        sort(nums, 0, len(nums)-1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        class Pair:\n",
    "            def __init__(self, val: int, id: int):\n",
    "                # 记录数组的元素值\n",
    "                self.val = val\n",
    "                # 记录元素在数组中的原始索引\n",
    "                self.id = id\n",
    "        \n",
    "        # 归并排序所用的辅助数组\n",
    "        temp = [Pair(0,0) for _ in range(len(nums))]\n",
    "        # 记录每个元素后面比自己小的元素个数\n",
    "        count = [0 for _ in range(len(nums))]\n",
    "        \n",
    "        # 归并排序\n",
    "        def sort(arr:List[Pair], lo:int, hi:int) -> None:\n",
    "            if lo == hi:\n",
    "                return\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            sort(arr, lo, mid)\n",
    "            sort(arr, mid + 1, hi)\n",
    "            merge(arr, lo, mid, hi)\n",
    "        \n",
    "        # 合并两个有序数组\n",
    "        def merge(arr:List[Pair], lo:int, mid:int, hi:int) -> None:\n",
    "            for i in range(lo, hi + 1):\n",
    "                temp[i] = arr[i]\n",
    "            \n",
    "            i, j = lo, mid + 1\n",
    "            for p in range(lo, hi + 1):\n",
    "                if i == mid + 1:\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                elif j == hi + 1:\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "                    # 更新 count 数组\n",
    "                    count[arr[p].id] += j - mid - 1\n",
    "                elif temp[i].val > temp[j].val:\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "                    # 更新 count 数组\n",
    "                    count[arr[p].id] += j - mid - 1\n",
    "\n",
    "        n = len(nums)\n",
    "        arr = [Pair(nums[i], i) for i in range(n)]\n",
    "        # 执行归并排序，本题结果被记录在 count 数组中\n",
    "        sort(arr, 0, n - 1)\n",
    "        \n",
    "        res = [c for c in count]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        class Pairs:\n",
    "            def __init__(self, idx, val):\n",
    "                self.idx = idx\n",
    "                self.val = val\n",
    "\n",
    "        length = len(nums)\n",
    "        tmp = [Pairs(0, 0) for _ in range(length)]\n",
    "        count = [0 for _ in range(length)]\n",
    "\n",
    "        def sort(arr: List[Pairs], lo: int, hi: int) -> None:\n",
    "            if lo == hi:\n",
    "                return\n",
    "\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            sort(arr, lo, mid)\n",
    "            sort(arr, mid + 1, hi)\n",
    "            merge_sort(arr, lo, mid, hi)\n",
    "\n",
    "        def merge_sort(arr: List[Pairs], lo: int, mid: int, hi: int) -> None:\n",
    "            for i in range(lo, hi + 1):\n",
    "                tmp[i] = arr[i]\n",
    "            i = lo\n",
    "            j = mid + 1\n",
    "            for p in range(lo, hi + 1):\n",
    "                # 左侧数组完成\n",
    "                if i == mid + 1:\n",
    "                    arr[p] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j == hi + 1:\n",
    "                    arr[p] = tmp[i]\n",
    "                    count[arr[p].idx] += j - mid - 1\n",
    "                    i += 1\n",
    "                elif tmp[i].val <= tmp[j].val:\n",
    "                    arr[p] = tmp[i]\n",
    "                    count[arr[p].idx] += j - mid - 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    arr[p] = tmp[j]\n",
    "                    j += 1\n",
    "\n",
    "        arr = [Pairs(i, nums[i]) for i in range(length)]\n",
    "        sort(arr, 0, length - 1)\n",
    "        return [c for c in count]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Recorder():\n",
    "    def __init__(self, val, index):\n",
    "        self.val = val\n",
    "        self.index = index\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        self.res = [0] * len(nums)\n",
    "        nums = [Recorder(nums[i], i) for i in range(len(nums))]\n",
    "        self.tmp = [Recorder(nums[i], i) for i in range(len(nums))]\n",
    "        left, right = 0, len(nums) - 1\n",
    "        \n",
    "\n",
    "        self.sort(nums, left, right)\n",
    "\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def sort(self, nums, left, right):\n",
    "        if left == right:\n",
    "            return \n",
    "        mid = left + (right-left) // 2\n",
    "        self.sort(nums, left, mid)\n",
    "        self.sort(nums, mid+1, right)\n",
    "        self.merge(nums, left, mid, right)\n",
    "\n",
    "        return\n",
    "\n",
    "    def merge(self, nums, left, mid, right):\n",
    "        for i in range(left, right+1):\n",
    "            self.tmp[i] = nums[i]\n",
    "        low, high = left, mid+1\n",
    "        for i in range(left, right+1):\n",
    "            if low == mid + 1:\n",
    "                nums[i] == self.tmp[high]\n",
    "                high += 1\n",
    "            elif high == right + 1:\n",
    "                nums[i] = self.tmp[low]\n",
    "                low += 1\n",
    "                self.res[nums[i].index] += high - mid - 1\n",
    "            elif self.tmp[low].val > self.tmp[high].val:\n",
    "                nums[i] = self.tmp[high]\n",
    "                high += 1\n",
    "            else:\n",
    "                nums[i] = self.tmp[low]\n",
    "                low += 1\n",
    "                self.res[nums[i].index] += high - mid - 1\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   # 归并是一种二分思路，可以用来解决多元素比较匹配问题，排序其实只是多元素比较的特殊情况之一\n",
    "   # 对于 5 2 6 1这样的数组，归并是二叉树的后续遍历\n",
    "   # 他的执行顺序是 5 2处理得2 5，6 1处理1 6，最后是汇总处理\n",
    "   # 由此你能发现每一次处理的时候，前面已经可以得出前半部分的结果，后面的结果和前面没有关系，因为前后被中间区分的索引分开了\n",
    "   # 由此得出贡献论：算一个元素后面的所有匹配，那就每一次递归的时候算当前递归的匹配，加上后面每一次的匹配即可\n",
    "\n",
    "   # 问题1： 我感觉直接算最后一次的匹配就可以啊？\n",
    "   # 最后一次的中间值是n/2，它其实之算了后半部分的贡献，前半部分的贡献丢了。所以正确答案是每一次递归的贡献加起来。\n",
    "\n",
    "   # 问题2： 每次贡献加起来，我感觉重复了啊？\n",
    "   # 单独看5 2的处理，的确是在汇总的时候又处理了一次，真的重复了！\n",
    "   # 关键点是：我们每次递归的时候是跟中间mid之后的元素比较，这样处理过的mid不断滚动，就没有重复了\n",
    "\n",
    "   # 问题3： 怎么能想到索引数组这个东西呢？\n",
    "   # 你不能想到它，是推理推出来的。首先你想我要不断的二分归并算符合条件的个数相加\n",
    "   # 相加之后的值存到哪里呢？应该是原来索引的对应位置啊！那我用dict啊，可是dict对于两个重复的数值会消失一个，不行\n",
    "   # 那我用一个元组对（数值，索引）这种元组，排序时用数值，取原来位置用索引。可以的！有的题解就是这种实现\n",
    "   # 好像这个（数值，索引）元组可以根据索引推出数值啊，为什么不用一个数组之存索引呢？\n",
    "   # 这就是索引数组啊，后面我们对这个索引数组对应的原始数组值排序，但是保持他们依然是索引\n",
    "\n",
    "   # 问题4：返回结果数组到底是用什么标记？索引数组的值？原始值？排序好的数组？排序好的索引数组？\n",
    "   # 都不是，应该需要一个新的结果数组，结果数组的值保存的是上面几个数组推理出来的结果汇总\n",
    "\n",
    "   # 问题5： 好乱，崩了！就算思路对了，随便一个地方写错就挂了！\n",
    "   # 所有长度，左右，加减1，值更新，比较，处理的地方写上注释：到底是操作的什么值？\n",
    "\n",
    "   #*** 核心思路：归并从左到右，以中间middle为界限，算middle后的贡献，算middle后的贡献！！ ***\n",
    "   #*** 以升序为标准，看右边小于左边值的个数： \n",
    "   #*** 1. 左右都有的情况，就是右边第一个大于等于左边值的索引距离中间的元素个数 \n",
    "   #*** 2. 左边有，右边空：就是所有右边数据条数\n",
    "   #*** 3. 右边有，左边空：就是0\n",
    "   #*** 4. 左右相等的情况怎么办？左边走，右边不动，这样相等处永远是第一个相等值，而且比前面的值大。那就可以用\n",
    "   def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "       def mergesort(low, high): # low/high分别对应开始结束索引，包含这两个索引本身！\n",
    "           if low == high: return # 索引一致，同一个数据嘛，不用比较，直接返回即可\n",
    "\n",
    "           # left,mid,right指的是索引数组的索引，不是索引数组的值，更不是原始值\n",
    "           mid = low + (high - low) //2 # 找到中间点，二分\n",
    "           mergesort(low, mid) # 左边处理\n",
    "           mergesort(mid+1, high) # 右边处理，注意右边从mid+1开始，保持总数据不漏不多，因为mergesort是包含开始结束索引的\n",
    "\n",
    "           # 后面这一坨，应该有个mergeall函数更好，要不自己能给看晕\n",
    "           # temp是升序排序\n",
    "           temp = [] # low-high之间排序好的新索引数组，后面替换成这个索引，相当于数据排序了，只是表现形式是索引\n",
    "           left, right = low, mid+1 # 以mid为中间值，和后面的比较，不能比较前面的，要不就重复处理了\n",
    "           while left <= mid or right <= high: # 左右分别在各自的半区间里边\n",
    "               if left > mid: # 索引数组左边都比较小，空了\n",
    "                   if right <= high: # 右边还有，那就跑完吧\n",
    "                       temp.append(inds[right]) # 放的值是原始数组的索引，也就是索引数组的[right]\n",
    "                       right += 1\n",
    "               elif right > high: # 索引数组右边都小，空了\n",
    "                   if left <= mid: # 左边还有，右边没了，那所有右边数据的条数就是更小数的个数\n",
    "                       temp.append(inds[left]) # temp是部分索引数组，所以放索引数组的值\n",
    "                       res[inds[left]] += right - mid -1 # 对于这一圈，右边有多少条数据，就是有多少个更小的结果\n",
    "                       left += 1\n",
    "               else: # 索引数组左右都有，那就比谁对应的原始数组值谁小吧\n",
    "                   # 左右相等为什么可以把结果也累加？相等应该是忽略啊？\n",
    "                   # 相等的时候我们只变化了左指针，右边没动，永远都是第一个相等值。\n",
    "                   # 所以相等处所有左边的值一定是比这个值小\n",
    "                   if nums[inds[left]] <= nums[inds[right]]: # 原始数组值比较大小\n",
    "                       temp.append(inds[left]) # 原始值小的话，把原始值对应的索引移动到temp里边\n",
    "                       res[inds[left]] += right - mid -1 # 结果数组以算有多少个更小的数\n",
    "                       left += 1\n",
    "                   else:\n",
    "                       temp.append(inds[right]) # 右边小，无法计算有多少个更小的，再跑一圈\n",
    "                       right += 1\n",
    "           inds[low:high+1] = temp[::] # 索引数组更新成排序好的新索引数组\n",
    "\n",
    "       m = len(nums) # m很有必要,要不你多个地方写len(nums),打错一个字符或者想错就挂了\n",
    "       res = [0] * m # 结果数组，保存的原始数组对应的后面又多少个更小值\n",
    "       inds = [i for i in range(m)] # 索引数组，后面我们不断对索引对应的原始值归并排序，并调整索引的位置\n",
    "       mergesort(0, m-1) # 两个参数都是有效的数组索引，不是第n个值！\n",
    "       return res\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        DC(l,m)\n",
    "        DC(m+1,r)\n",
    "\n",
    "        Merge(l,m,r)\n",
    "\n",
    "        '''\n",
    "        count = [0]*(len(nums))\n",
    "        index = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            index[i] = i\n",
    "\n",
    "        def DivideSort(count,l,r):\n",
    "            if l>=r:\n",
    "                return\n",
    "            if r-l==1:\n",
    "                if nums[l]>nums[r]:\n",
    "                    count[index[l]]+=1\n",
    "                    return\n",
    "                else:\n",
    "                    nums[l],nums[r] = nums[r],nums[l]\n",
    "                    index[l],index[r] = index[r],index[l]\n",
    "                    return\n",
    "            mid = (l+r)//2\n",
    "            DivideSort(count,mid+1,r)\n",
    "            DivideSort(count,l,mid)\n",
    "\n",
    "            #merge\n",
    "            temp = []\n",
    "            temp1 = []\n",
    "            left = l\n",
    "            mid = (l+r)//2\n",
    "            right = mid + 1\n",
    "            for i in range(l,mid+1):\n",
    "                '''\n",
    "                while nums[right]>=nums[i] and right<=r:\n",
    "                    temp.append(nums[right])\n",
    "                    temp1.append(index[right])\n",
    "                    right+=1\n",
    "                '''\n",
    "                while right<=r:\n",
    "                    if nums[right]>=nums[i]:\n",
    "                        temp.append(nums[right])\n",
    "                        temp1.append(index[right])\n",
    "                        right += 1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                temp.append(nums[i])\n",
    "                temp1.append(index[i])\n",
    "                count[index[i]]+= r-right+1\n",
    "            while right<=r:\n",
    "                temp.append(nums[right])\n",
    "                temp1.append(index[right])\n",
    "                right+=1\n",
    "\n",
    "            #debug\n",
    "            #print(temp)\n",
    "            for j in range(l,r+1):\n",
    "                nums[j] = temp[j-l]\n",
    "                index[j] = temp1[j-l]\n",
    "\n",
    "        DivideSort(count,0,len(nums)-1)\n",
    "\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        if not nums or len(nums)==1:\n",
    "            return [0]\n",
    "        index=[i for i in range(len(nums))]\n",
    "        ans_index=[0 for i in range(len(nums))]\n",
    "        def mergesort(l,r):\n",
    "            if l>=r:\n",
    "                return \n",
    "\n",
    "            mid=(l+r)//2\n",
    "            mergesort(l,mid)\n",
    "            mergesort(mid+1,r)\n",
    "\n",
    "            i,j=l,mid+1\n",
    "            tmp=[]\n",
    "            tmp_indx=[]\n",
    "                \n",
    "            while i<=mid and j<=r:\n",
    "                if nums[i]<=nums[j]:\n",
    "                    tmp.append(nums[i])\n",
    "                    tmp_indx.append(index[i])\n",
    "                    ans_index[index[i]] += (j - mid - 1)\n",
    "\n",
    "                    i+=1\n",
    "                else:\n",
    "                    tmp.append(nums[j])\n",
    "                    tmp_indx.append(index[j])\n",
    "                    j += 1     \n",
    "\n",
    "            while i<=mid:\n",
    "                tmp.append(nums[i])\n",
    "                tmp_indx.append(index[i])\n",
    "                if nums[i]!=nums[r]:\n",
    "                    ans_index[index[i]]+=(j-mid-1)\n",
    "\n",
    "                i+=1                       \n",
    "            while j<=r:\n",
    "                tmp.append(nums[j])\n",
    "                tmp_indx.append(index[j])\n",
    "                j+=1\n",
    "\n",
    "\n",
    "            nums[l:r+1]=tmp\n",
    "            index[l:r+1]=tmp_indx\n",
    "\n",
    "        mergesort(0,len(nums)-1)\n",
    "        return ans_index\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        if not nums or len(nums)==1:\n",
    "            [0]\n",
    "        index=[i for i in range(len(nums))]\n",
    "        ans_index=[0 for i in range(len(nums))]\n",
    "        def mergesort(l,r):\n",
    "            if l>=r:\n",
    "                return\n",
    "            mid=(l+r)//2\n",
    "            mergesort(l,mid)\n",
    "            mergesort(mid+1,r)\n",
    "            i,j=l,mid+1\n",
    "            tmp=[]\n",
    "            tmp_indx=[]\n",
    "            while i<mid+1 or j<r+1:\n",
    "                if i==mid+1:\n",
    "                    tmp.append(nums[j])\n",
    "                    tmp_indx.append(index[j])\n",
    "                    j+=1\n",
    "                elif j==r+1:\n",
    "                    tmp.append(nums[i])\n",
    "                    tmp_indx.append(index[i])\n",
    "                    if nums[i]!=nums[r]:\n",
    "                        ans_index[index[i]]+=(j-mid-1)\n",
    "                    i+=1\n",
    "                elif nums[i]<=nums[j]:\n",
    "                    tmp.append(nums[i])\n",
    "                    tmp_indx.append(index[i])\n",
    "                    ans_index[index[i]] += (j - mid - 1)\n",
    "                    i+=1\n",
    "                else:\n",
    "                    tmp.append(nums[j])\n",
    "                    tmp_indx.append(index[j])\n",
    "                    j += 1\n",
    "            nums[l:r+1]=tmp\n",
    "            index[l:r+1]=tmp_indx\n",
    "        mergesort(0,len(nums)-1)\n",
    "        return ans_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def merge(left,right):###right=n\n",
    "            if left>=right-1:\n",
    "                return \n",
    "            mid = (left+right) //2\n",
    "            merge(left,mid)\n",
    "            merge(mid,right)\n",
    "            mergesort(left,mid,right)\n",
    "\n",
    "\n",
    "        def mergesort(l,m,r):\n",
    "            tmp = [0] * (r-l)\n",
    "            il = l\n",
    "            ir = m\n",
    "            i = 0\n",
    "            tmp1 = [index[i] for i in range(l,m)]\n",
    "            tmp2 = [index[i] for i in range(m,r)]\n",
    "\n",
    "            while il<m and ir<r:\n",
    "\n",
    "                if nums[index[il]] <= nums[index[ir]]:\n",
    "                    tmp[i] = index[il]\n",
    "                    res[index[il]] += ir-m\n",
    "                    # print(f'{il}没加完此时{index[il]}加{ir-m}')\n",
    "                    i += 1\n",
    "                    il += 1\n",
    "                    \n",
    "                    \n",
    "                else:\n",
    "                    # print(f'{ir}不用换顺序此时{index[ir]}')\n",
    "                    tmp[i] = index[ir]\n",
    "                    i += 1\n",
    "                    ir += 1\n",
    "            while il<m:\n",
    "                tmp[i] =index[il]\n",
    "                res[index[il]] += r-m\n",
    "                # print(f'加完了此时{index[il]}加1')\n",
    "                i += 1\n",
    "                il += 1\n",
    "            while ir< r:\n",
    "                tmp[i] = index[ir]\n",
    "                i += 1\n",
    "                ir += 1\n",
    "            for i in range(r-l):\n",
    "                index[l+i] = tmp[i]\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        res = [0] * n               # 存储结果\n",
    "        index = list(range(n))      # 索引数组\n",
    "        merge(0, n)     # 归并排序\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\r\n",
    "        idxs = list(range(len(nums)))\r\n",
    "        counts = [0] * len(nums)\r\n",
    "\r\n",
    "        def mergesort(left, right):\r\n",
    "            if right - left == 1:\r\n",
    "                return \r\n",
    "            mid = left + (right-left)//2\r\n",
    "\r\n",
    "            mergesort(left, mid)\r\n",
    "            mergesort(mid, right)\r\n",
    "\r\n",
    "            # 已经有序，nums[i]右侧不会有比其小的元素\r\n",
    "            if nums[mid-1] <= nums[mid]:\r\n",
    "                return \r\n",
    "\r\n",
    "            merge(left, mid, right)\r\n",
    "\r\n",
    "        def merge(left, mid, right):\r\n",
    "            aux_i = idxs[left:right]\r\n",
    "            aux = nums[left:right]\r\n",
    "            i = 0\r\n",
    "            j = mid-left\r\n",
    "\r\n",
    "            for k in range(left, right):\r\n",
    "                if i == mid-left:\r\n",
    "                    nums[k] = aux[j]\r\n",
    "                    idxs[k] = aux_i[j]\r\n",
    "                    j += 1\r\n",
    "                elif j == right-left:\r\n",
    "                    nums[k] = aux[i]\r\n",
    "                    idxs[k] = aux_i[i]\r\n",
    "                    counts[aux_i[i]] += j-mid+left\r\n",
    "                    i += 1\r\n",
    "                elif aux[i] > aux[j]:\r\n",
    "                    nums[k] = aux[j]\r\n",
    "                    idxs[k] = aux_i[j]\r\n",
    "                    j += 1\r\n",
    "                else:\r\n",
    "                    nums[k] = aux[i]\r\n",
    "                    idxs[k] = aux_i[i]\r\n",
    "                    counts[aux_i[i]] += j-mid+left\r\n",
    "                    i += 1\r\n",
    "        mergesort(0, len(nums))\r\n",
    "    \r\n",
    "        return counts\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def merge_sort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "\n",
    "            mid = (l+r) >> 1\n",
    "            merge_sort(l, mid)\n",
    "            merge_sort(mid+1, r)\n",
    "            merge(l, mid, r)\n",
    "\n",
    "        def merge(l, mid, r):\n",
    "            nonlocal ans, nums\n",
    "            tmp = index[l:r+1]\n",
    "            l1, l2 = l, mid+1\n",
    "            for i in range(l, r+1):\n",
    "                if l2 > r:\n",
    "                    ans[tmp[l1-l]] += r-mid\n",
    "                    index[i] = tmp[l1-l]\n",
    "                    l1 += 1\n",
    "\n",
    "                elif l1 > mid:\n",
    "                    index[i] = tmp[l2-l]\n",
    "                    l2 += 1 \n",
    "                \n",
    "                elif nums[tmp[l1-l]] <= nums[tmp[l2-l]]:\n",
    "                    ans[tmp[l1-l]] += l2-mid-1\n",
    "                    index[i] = tmp[l1-l]\n",
    "                    l1 += 1\n",
    "                \n",
    "                else:\n",
    "                    index[i] = tmp[l2-l]\n",
    "                    l2 += 1\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = [0 for _ in range(n)]\n",
    "        index = [i for i in range(n)]\n",
    "        merge_sort(0, n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        counts = [0] * len(nums)\n",
    "        index = [i for i in range(len(nums))]\n",
    "\n",
    "        def Merge_sort(low, high):\n",
    "            if high - low < 2:\n",
    "                return\n",
    "            mid =  low + (high - low) // 2\n",
    "            Merge_sort(low, mid)\n",
    "            Merge_sort(mid, high)\n",
    "            Merge(low, mid, high)\n",
    "        \n",
    "        def Merge(low, mid, high):\n",
    "            tmp = mid\n",
    "            pre = low\n",
    "            res = []\n",
    "            while low < mid or tmp < high:\n",
    "                if low == mid or (tmp < high and nums[index[low]] <= nums[index[tmp]]):\n",
    "                    res.append(index[tmp])\n",
    "                    tmp += 1\n",
    "                else:\n",
    "                    res.append(index[low])\n",
    "                    counts[index[low]] += high - tmp\n",
    "                    low += 1\n",
    "\n",
    "            index[pre: high] = res\n",
    "        \n",
    "        Merge_sort(0, len(nums))\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]: \n",
    "        n = len(nums)\n",
    "        count = [0]*n\n",
    "        idxarr = [i for i in range(n)]\n",
    "        def mergersort(nums,l,r):\n",
    "            if l>=r:\n",
    "                return\n",
    "            mid = l + ((r-l)>>1)\n",
    "            mergersort(nums,l,mid)\n",
    "            mergersort(nums,mid+1,r)\n",
    "            merge(nums,l,mid,r)\n",
    "        # 实现降序归并\n",
    "        def merge(arr,l,mid,r):\n",
    "            i1,i2 = l,mid+1\n",
    "            temparr = [0]*(r-l+1) # 用于临时存放排好序的数组\n",
    "            cur = 0\n",
    "            tempidx = [0]*(r-l+1) # 临时存放位置索引的变化\n",
    "\n",
    "            while i1<=mid and i2<=r:\n",
    "                if nums[i1]>nums[i2]:\n",
    "                    count[idxarr[i1]] += r-i2+1\n",
    "                    tempidx[cur] = idxarr[i1] # 元素的位置改变，临时记录位置的变化\n",
    "                    temparr[cur] = nums[i1]\n",
    "                    i1+=1\n",
    "                else:\n",
    "                    temparr[cur] = nums[i2]\n",
    "                    tempidx[cur] = idxarr[i2]\n",
    "                    i2+=1\n",
    "                cur +=1\n",
    "            \n",
    "            while i2<=r:\n",
    "                temparr[cur]=nums[i2]\n",
    "                tempidx[cur] = idxarr[i2]\n",
    "                i2+=1\n",
    "                cur+=1\n",
    "            \n",
    "            while i1<=mid:\n",
    "                tempidx[cur] = idxarr[i1]\n",
    "                temparr[cur] = nums[i1]\n",
    "                i1+=1\n",
    "                cur+=1\n",
    "            # 更新数组，和对应的位置索引的变化\n",
    "            for i in range(l,r+1):\n",
    "                nums[i] = temparr[i-l]\n",
    "                idxarr[i] = tempidx[i-l]\n",
    "        mergersort(nums,0,n-1)\n",
    "        return count\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        ans = [0] * n\r\n",
    "        indices = [i for i in range(n)]\r\n",
    "\r\n",
    "        def merge(left, mid, right):\r\n",
    "            tmp_nums = nums[left: right][:]\r\n",
    "            tmp_indices = indices[left: right][:]\r\n",
    "\r\n",
    "            i, j, k = left, mid, 0\r\n",
    "            while i < mid and j < right:\r\n",
    "                if nums[j] < nums[i]:\r\n",
    "                    tmp_nums[k] = nums[j]\r\n",
    "                    tmp_indices[k] = indices[j]\r\n",
    "                    k += 1\r\n",
    "                    j += 1\r\n",
    "                else:\r\n",
    "                    tmp_nums[k] = nums[i]\r\n",
    "                    tmp_indices[k] = indices[i]\r\n",
    "                    ans[indices[i]] += j - mid\r\n",
    "                    k += 1\r\n",
    "                    i += 1\r\n",
    "                    \r\n",
    "            while i < mid:\r\n",
    "                tmp_nums[k] = nums[i]\r\n",
    "                tmp_indices[k] = indices[i]\r\n",
    "                ans[indices[i]] += j - mid\r\n",
    "                k += 1\r\n",
    "                i += 1\r\n",
    "            while j < right:\r\n",
    "                tmp_nums[k] = nums[j]\r\n",
    "                tmp_indices[k] = indices[j]\r\n",
    "                k += 1\r\n",
    "                j += 1\r\n",
    "            nums[left: right] = tmp_nums\r\n",
    "            indices[left: right] = tmp_indices\r\n",
    "        \r\n",
    "        def mergeSort(left, right):\r\n",
    "            # print('sort', nums[left: right])\r\n",
    "            if right - left <= 1:\r\n",
    "                return\r\n",
    "            mid = (left + right) // 2\r\n",
    "            mergeSort(left, mid)\r\n",
    "            mergeSort(mid, right)\r\n",
    "            merge(left, mid, right)\r\n",
    "        \r\n",
    "        mergeSort(0, n)\r\n",
    "        # print(nums)\r\n",
    "        # print(indices)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        index = [i for i in range(len(nums))]  # 表示当前下标为 i 的元素在原数组中的下标\n",
    "        ans = [0] * len(nums)\n",
    "\n",
    "        def merge_sort(l, r):\n",
    "            if l >= r:\n",
    "                return \n",
    "            m = l + (r - l) // 2\n",
    "            merge_sort(l, m)\n",
    "            merge_sort(m + 1, r)\n",
    "            merge(l, m, r)\n",
    "\n",
    "        def merge(l, m, r):\n",
    "            i = l\n",
    "            j = m + 1\n",
    "            tmp_index = [0] * (r - l + 1)\n",
    "            tmp = [0] * (r - l + 1)\n",
    "            \n",
    "            for k in range(l, r + 1):\n",
    "                idx = k - l\n",
    "                if i == m + 1:\n",
    "                    tmp[idx] = nums[j]\n",
    "                    tmp_index[idx] = index[j]\n",
    "                    j += 1\n",
    "                elif j == r + 1:\n",
    "                    tmp[idx] = nums[i]\n",
    "                    tmp_index[idx] = index[i]\n",
    "                    i += 1\n",
    "                elif nums[i] > nums[j]:\n",
    "                    tmp[idx] = nums[i]\n",
    "                    ans[index[i]] += r - j + 1\n",
    "                    tmp_index[idx] = index[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp[idx] = nums[j]\n",
    "                    tmp_index[idx] = index[j]\n",
    "                    j += 1\n",
    "            \n",
    "            nums[l: r + 1] = tmp[:]\n",
    "            index[l: r + 1] = tmp_index[:]\n",
    "        merge_sort(0, len(nums) - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        index = [i for i in range(n)]  # 表示更换后位置到原来位置的映射\n",
    "\n",
    "        def mergeSort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            mergeSort(l, m)\n",
    "            mergeSort(m+1, r)\n",
    "            i, j, p = l, m+1, 0\n",
    "            tmp = [0]*(r-l+1)\n",
    "            tmp_index = [0]*(r-l+1)\n",
    "            while i <= m and j <= r:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    tmp[p] = nums[i]\n",
    "                    tmp_index[p] = index[i]\n",
    "                    ans[index[i]] += (j-m-1)\n",
    "                    p += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp[p] = nums[j]\n",
    "                    tmp_index[p] = index[j]\n",
    "                    p += 1\n",
    "                    j += 1\n",
    "            while i <= m:\n",
    "                tmp[p] = nums[i]\n",
    "                tmp_index[p] = index[i]\n",
    "                ans[index[i]] += (j-m-1)\n",
    "                p += 1\n",
    "                i += 1\n",
    "            while j <= r:\n",
    "                tmp[p] = nums[j]\n",
    "                tmp_index[p] = index[j]\n",
    "                p += 1\n",
    "                j += 1\n",
    "            nums[l:r+1] = tmp\n",
    "            index[l:r+1] = tmp_index\n",
    "        mergeSort(0, n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        # print(a)\n",
    "\n",
    "        pre_sum = [0] * len(a)\n",
    "\n",
    "        def lowbit(x):\n",
    "            return x & (-x)\n",
    "\n",
    "        def update(index):\n",
    "            \n",
    "            index += 1\n",
    "\n",
    "            while index < len(a):\n",
    "                pre_sum[index] += 1\n",
    "                index += lowbit(index)\n",
    "\n",
    "        def query(index):\n",
    "            res = 0\n",
    "            while index > 0:\n",
    "                res += pre_sum[index]\n",
    "                index -= lowbit(index)\n",
    "\n",
    "            return res\n",
    "\n",
    "        ans = [0] * len(nums)\n",
    "\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            a_index = bisect.bisect_left(a, nums[i])\n",
    "            update(a_index)\n",
    "            ans[i] = query(a_index)\n",
    "\n",
    "        return ans\n",
    "        '''\n",
    "        tmp = [0] * len(nums)\n",
    "        indexes = [i for i in range(len(nums))]\n",
    "        ans = [0] * len(nums)\n",
    "\n",
    "        def mergeAndCounterSmaller(left, right, mid):\n",
    "            for i in range(left, right + 1):\n",
    "                tmp[i] = indexes[i]\n",
    "\n",
    "            i, j = left, mid + 1\n",
    "            k = left\n",
    "            for k in range(left, right + 1):\n",
    "                if i > mid:\n",
    "                    indexes[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j > right:\n",
    "                    indexes[k] = tmp[i]\n",
    "                    ans[indexes[k]] += right - mid\n",
    "                    i += 1\n",
    "                elif nums[tmp[i]] <= nums[tmp[j]]:\n",
    "                    indexes[k] = tmp[i]\n",
    "                    i += 1\n",
    "                    ans[indexes[k]] += j - mid - 1\n",
    "                else:\n",
    "                    indexes[k] = tmp[j]\n",
    "                    j += 1\n",
    "\n",
    "        def merge(left, right):\n",
    "            if left == right:\n",
    "                return \n",
    "\n",
    "            mid = (left + right) // 2\n",
    "            merge(left, mid)\n",
    "            merge(mid + 1, right)\n",
    "\n",
    "            if nums[indexes[mid]] <= nums[indexes[mid + 1]]:\n",
    "                return \n",
    "            mergeAndCounterSmaller(left, right, mid)\n",
    "\n",
    "        merge(0, len(nums) - 1)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Pair:\n",
    "\n",
    "    def __init__(self, identity, val):\n",
    "        self.id = identity\n",
    "        self.val = val\n",
    "\n",
    "    def __gt__(self, other):\n",
    "        return self.val > other.val\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        countMap = {i: 0 for i in range(len(nums))}\n",
    "\n",
    "        def mergeSort(data, left, right):\n",
    "            if left >= right:\n",
    "                return\n",
    "\n",
    "            mid = left + (right - left) // 2\n",
    "            mergeSort(data, left, mid)\n",
    "            mergeSort(data, mid + 1, right)\n",
    "\n",
    "            tmp[left:right + 1] = data[left:right + 1]\n",
    "            lo, hi = left, mid + 1\n",
    "            for p in range(left, right + 1):\n",
    "                if lo == mid + 1:\n",
    "                    data[p] = tmp[hi]\n",
    "                    hi += 1\n",
    "                elif hi == right + 1:\n",
    "                    data[p] = tmp[lo]\n",
    "                    lo += 1\n",
    "                    countMap[data[p].id] += (hi - mid - 1)\n",
    "                elif tmp[lo] > tmp[hi]:\n",
    "                    data[p] = tmp[hi]\n",
    "                    hi += 1\n",
    "                else:\n",
    "                    data[p] = tmp[lo]\n",
    "                    lo += 1\n",
    "                    countMap[data[p].id] += (hi - mid - 1)\n",
    "\n",
    "        arr = [Pair(identity=i, val=nums[i]) for i in range(len(nums))]\n",
    "        tmp = arr[::]\n",
    "        mergeSort(arr, 0, len(nums) - 1)\n",
    "\n",
    "        return [countMap[i] for i in range(len(nums))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def merge_sort(a, l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            mid = l + (r - l) // 2\n",
    "            merge_sort(a, l, mid)\n",
    "            merge_sort(a, mid+1, r)\n",
    "            merge(a, l, mid, r)\n",
    "\n",
    "        def merge(a, l, mid, r):\n",
    "            i, j = l, mid + 1\n",
    "            p = l\n",
    "            while i <= mid and j <=r:\n",
    "                if a[i] <= a[j]:\n",
    "                    temp[p] = a[i]\n",
    "                    temp_index[p] = index[i]\n",
    "                    ans[index[i]] += (j - mid - 1)\n",
    "                    i += 1\n",
    "                    p += 1\n",
    "                else:\n",
    "                    temp[p] = a[j]\n",
    "                    temp_index[p] = index[j]\n",
    "                    j += 1\n",
    "                    p += 1\n",
    "            while i <= mid:\n",
    "                temp[p] = a[i]\n",
    "                temp_index[p] = index[i]\n",
    "                ans[index[i]] += (j - mid - 1)\n",
    "                i += 1\n",
    "                p += 1\n",
    "            while j <= r:\n",
    "                temp[p] = a[j]\n",
    "                temp_index[p] = index[j]\n",
    "                j += 1\n",
    "                p += 1\n",
    "            \n",
    "            for i in range(l, r+1):\n",
    "                a[i] = temp[i]\n",
    "                index[i] = temp_index[i]\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        index = list(range(n))\n",
    "        temp = [0] * n\n",
    "        temp_index = [0] * n\n",
    "        merge_sort(nums, 0, n-1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        def merge(arr, l, mid, r):\n",
    "            i, j, p = l, mid + 1, l\n",
    "            while i <= mid and j <= r:\n",
    "                if arr[i] <= arr[j]:\n",
    "                    temp[p] = arr[i]\n",
    "                    temp_index[p] = index[i]\n",
    "                    ans[index[i]] += j - mid - 1\n",
    "                    i += 1\n",
    "                    p += 1\n",
    "                else:\n",
    "                    temp[p] = arr[j]\n",
    "                    temp_index[p] = index[j]\n",
    "                    j += 1\n",
    "                    p += 1\n",
    "            while i <= mid:\n",
    "                temp[p] = arr[i]\n",
    "                temp_index[p] = index[i]\n",
    "                ans[index[i]] += j - mid - 1\n",
    "                i += 1\n",
    "                p += 1\n",
    "            while j <= r:\n",
    "                temp[p] = arr[j]\n",
    "                temp_index[p] = index[j]\n",
    "                j += 1\n",
    "                p += 1\n",
    "            for k in range(l, r+1):\n",
    "                index[k] = temp_index[k]\n",
    "                arr[k] = temp[k] \n",
    "\n",
    "        def merge_sort(arr, l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            mid = l + ((r - l) >> 1)\n",
    "            merge_sort(arr, l, mid)\n",
    "            merge_sort(arr, mid + 1, r)\n",
    "            merge(arr, l, mid , r)\n",
    "\n",
    "        index = [i for i in range(len(nums))]\n",
    "        temp = [0] * len(nums)\n",
    "        temp_index = [0] * len(nums)\n",
    "        ans =  [0] * len(nums)\n",
    "        l, r = 0, len(nums) - 1\n",
    "        merge_sort(nums, l, r)\n",
    "\n",
    "        return ans\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pair:\n",
    "    def __init__(self, index = 0, val = 0):\n",
    "        self.val = val\n",
    "        self.index = index\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        self.tmp = [Pair() for i in range(n)]\n",
    "        tmpNums = [Pair(i, v) for i, v in enumerate(nums)]\n",
    "        self.d = dict()\n",
    "        for i, v in enumerate(nums):\n",
    "            self.d[i] = 0\n",
    "        def recurse(tmp_nums, l, m ,r):\n",
    "            for i in range(l, r + 1):\n",
    "                self.tmp[i] = tmp_nums[i]\n",
    "            l_index, r_index = l, m + 1\n",
    "            for i in range(l, r + 1):\n",
    "                if l_index > m:\n",
    "                    tmp_nums[i] = self.tmp[r_index]\n",
    "                    r_index += 1\n",
    "                elif r_index > r:\n",
    "                    tmp_nums[i] = self.tmp[l_index]\n",
    "                    self.d[tmp_nums[i].index] += r_index - m - 1\n",
    "                    l_index += 1\n",
    "                elif self.tmp[l_index].val > self.tmp[r_index].val:\n",
    "                    tmp_nums[i] = self.tmp[r_index]\n",
    "                    r_index += 1\n",
    "                else:\n",
    "                    tmp_nums[i] = self.tmp[l_index]\n",
    "                    self.d[tmp_nums[i].index] += r_index - m - 1\n",
    "                    l_index += 1\n",
    "        def sort(tmp_nums, l, r):\n",
    "            if l == r:\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            sort(tmp_nums, l, mid)\n",
    "            sort(tmp_nums, mid + 1, r)\n",
    "            recurse(tmp_nums, l, mid, r)\n",
    "        sort(tmpNums, 0, n - 1)\n",
    "        for i in range(n):\n",
    "            res[i] = self.d[i]\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        indices = list(range(n))\n",
    "        counts = [0] * n\n",
    "\n",
    "        tmp = [0] * n\n",
    "        tmp_idx = [0] * n\n",
    "        def merge(arr, left, mid, right):\n",
    "            end = mid + 1\n",
    "            for i in range(left, mid + 1):\n",
    "                while end <= right and arr[i] > arr[end]:\n",
    "                    end += 1\n",
    "                counts[indices[i]] += end - mid - 1\n",
    "\n",
    "            idx = left\n",
    "            i, j = left, mid + 1\n",
    "            while i <= mid and j <= right:\n",
    "                if arr[i] <= arr[j]:\n",
    "                    tmp[idx] = arr[i]\n",
    "                    tmp_idx[idx] = indices[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp[idx] = arr[j]\n",
    "                    tmp_idx[idx] = indices[j]\n",
    "                    j += 1\n",
    "                idx += 1\n",
    "            \n",
    "            while i <= mid:\n",
    "                tmp[idx] = arr[i]\n",
    "                tmp_idx[idx] = indices[i]\n",
    "                i += 1\n",
    "                idx += 1\n",
    "            \n",
    "            while j <= right:\n",
    "                tmp[idx] = arr[j]\n",
    "                tmp_idx[idx] = indices[j]\n",
    "                j += 1\n",
    "                idx += 1\n",
    "            \n",
    "            arr[left:right + 1] = tmp[left:right + 1]\n",
    "            indices[left:right + 1] = tmp_idx[left:right + 1]\n",
    "\n",
    "        def sort(arr, left, right):\n",
    "            if left >= right:\n",
    "                return \n",
    "            \n",
    "            mid = (left + right) // 2\n",
    "            sort(arr, left, mid)\n",
    "            sort(arr, mid + 1, right)\n",
    "            merge(arr, left, mid, right)\n",
    "\n",
    "        sort(nums, 0, n - 1)\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countSmaller(self, nums):\n",
    "        n = len(nums)\n",
    "        tmp = [0] * n\n",
    "        res = [0] * n\n",
    "        tempIndex = [0] * n\n",
    "        index = [0] * n\n",
    "        for i in range(n):\n",
    "            index[i] = i\n",
    "\n",
    "        def mergeSort(l, r):\n",
    "            if l == r:\n",
    "                return 0\n",
    "            mid = l + (r - l) // 2\n",
    "            mergeSort(l, mid)\n",
    "            mergeSort(mid + 1, r)\n",
    "            i, j, pos = l, mid + 1, l\n",
    "            while i <= mid and j <= r:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    tmp[pos] = nums[i]\n",
    "                    tempIndex[pos] = index[i]\n",
    "                    res[index[i]] += (j - (mid + 1))\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp[pos] = nums[j]\n",
    "                    tempIndex[pos] = index[j]\n",
    "                    j += 1\n",
    "                pos += 1\n",
    "\n",
    "            for k in range(i, mid + 1):\n",
    "                tmp[pos] = nums[k]\n",
    "                tempIndex[pos] = index[k]\n",
    "                res[index[k]] += (j - (mid + 1))\n",
    "                pos += 1\n",
    "            for k in range(j, r + 1):\n",
    "                tmp[pos] = nums[k]\n",
    "                tempIndex[pos] = index[k]\n",
    "                pos += 1\n",
    "\n",
    "            nums[l:r + 1] = tmp[l:r + 1]\n",
    "            index[l:r + 1] = tempIndex[l:r + 1]\n",
    "            return\n",
    "\n",
    "        mergeSort(0, n - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n \n",
    "        index = list(range(n))\n",
    "        tmp_index = index[:]\n",
    "        tmp = [0] * n \n",
    "        def merge(start, end):\n",
    "            # nonlocal res \n",
    "            mid = start + (end - start) // 2 \n",
    "            j = mid + 1\n",
    "            for i in range(start, mid + 1):\n",
    "                while j <= end and nums[j] < nums[i]:\n",
    "                    j += 1\n",
    "                res[index[i]] += j - mid - 1 \n",
    "            i, j, p = start, mid + 1, start\n",
    "            while i <= mid and j <= end:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    tmp_index[p] = index[i]\n",
    "                    tmp[p] = nums[i]\n",
    "                    i += 1 \n",
    "                else:\n",
    "                    tmp_index[p] = index[j]\n",
    "                    tmp[p] = nums[j]\n",
    "                    j += 1 \n",
    "                p += 1 \n",
    "            while i <= mid:\n",
    "                tmp_index[p] = index[i]\n",
    "                tmp[p] = nums[i]\n",
    "                i += 1 \n",
    "                p += 1 \n",
    "            while j <= end:\n",
    "                tmp_index[p] = index[j]\n",
    "                tmp[p] = nums[j]\n",
    "                j += 1 \n",
    "                p += 1\n",
    "            for i in range(start, end + 1):\n",
    "                nums[i] = tmp[i]\n",
    "                index[i] = tmp_index[i]\n",
    "        \n",
    "        def merge_sort(start, end):\n",
    "            if start == end:\n",
    "                return \n",
    "            mid = start + (end - start) // 2 \n",
    "            merge_sort(start, mid)\n",
    "            merge_sort(mid + 1, end)\n",
    "            merge(start, end)\n",
    "        merge_sort(0, n - 1)\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        proc=[0]*n\n",
    "        procindex=[0]*n\n",
    "        index=[0]*n\n",
    "        for i in range(n) :\n",
    "            index[i]=i\n",
    "        def combine(l,mid,r) :\n",
    "            i,j,t=l,mid+1,0\n",
    "            while i<=mid and j<=r :\n",
    "                if nums[i]<=nums[j] :\n",
    "                    ans[index[i]]+=j-mid-1\n",
    "                    proc[t]=nums[i]\n",
    "                    procindex[t]=index[i]\n",
    "                    t+=1\n",
    "                    i+=1\n",
    "                else :\n",
    "                    proc[t]=nums[j]\n",
    "                    procindex[t]=index[j]\n",
    "                    t+=1\n",
    "                    j+=1\n",
    "            while i<=mid :\n",
    "                ans[index[i]]+=j-mid-1\n",
    "                proc[t]=nums[i]\n",
    "                procindex[t]=index[i]\n",
    "                t+=1\n",
    "                i+=1\n",
    "            while j<=r :\n",
    "                proc[t]=nums[j]\n",
    "                procindex[t]=index[j]\n",
    "                t+=1\n",
    "                j+=1\n",
    "            for i in range(t) :\n",
    "                nums[i+l]=proc[i]\n",
    "                index[i+l]=procindex[i]\n",
    "        def divide(l,r) :\n",
    "            if l<r :\n",
    "                mid=(l+r)//2\n",
    "                divide(l,mid)\n",
    "                divide(mid+1,r)\n",
    "                combine(l,mid,r)\n",
    "        divide(0,n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def merageSort(self, nums, tmp1, left, right, ans, index, tmp2):\n",
    "    #     if left >= right:\n",
    "    #         return\n",
    "    #     mid = left + (right - left) // 2\n",
    "    #     self.merageSort(nums, tmp1, left, mid, ans, index, tmp2)\n",
    "    #     self.merageSort(nums, tmp1, mid + 1, right, ans, index, tmp2)\n",
    "    #     # [left, mid]   [mid+1, right]\n",
    "    #     i, cur1, cur2 = left, left, mid + 1\n",
    "    #     while cur1 <= mid and cur2 <= right:\n",
    "    #         if nums[cur1] <= nums[cur2]:\n",
    "    #             tmp1[i] = nums[cur2]\n",
    "    #             tmp2[i] = index[cur2]\n",
    "    #             cur2 += 1\n",
    "    #         else:\n",
    "    #             tmp1[i] = nums[cur1]\n",
    "    #             tmp2[i] = index[cur1]\n",
    "    #             ans[index[cur1]] += right - cur2 + 1\n",
    "    #             cur1 += 1\n",
    "    #         i += 1\n",
    "    #     while cur1 <= mid:\n",
    "    #         tmp1[i] = nums[cur1]\n",
    "    #         tmp2[i] = index[cur1]\n",
    "    #         cur1 += 1\n",
    "    #         i += 1\n",
    "    #     while cur2 <= right:\n",
    "    #         tmp1[i] = nums[cur2]\n",
    "    #         tmp2[i] = index[cur2]\n",
    "    #         cur2 += 1\n",
    "    #         i += 1\n",
    "    #     nums[left:right + 1] = tmp1[left:right + 1]\n",
    "    #     index[left:right + 1] = tmp2[left:right + 1]\n",
    "\n",
    "\n",
    "    def countSmaller(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        index = [i for i in range(0, n)]\n",
    "        ans, tmp1, tmp2 = [0] * n, [0] * n, [0] * n\n",
    "        # self.merageSort(nums, tmp1, 0, n - 1, ans, index, tmp2)\n",
    "        def merageSort(left, right):\n",
    "            if left >= right:\n",
    "                return\n",
    "            mid = left + (right - left) // 2\n",
    "            merageSort(left, mid)\n",
    "            merageSort(mid + 1, right)\n",
    "            # [left, mid]   [mid+1, right]\n",
    "            i, cur1, cur2 = left, left, mid + 1\n",
    "            while cur1 <= mid and cur2 <= right:\n",
    "                if nums[cur1] <= nums[cur2]:\n",
    "                    tmp1[i] = nums[cur2]\n",
    "                    tmp2[i] = index[cur2]\n",
    "                    cur2 += 1\n",
    "                else:\n",
    "                    tmp1[i] = nums[cur1]\n",
    "                    tmp2[i] = index[cur1]\n",
    "                    ans[index[cur1]] += right - cur2 + 1\n",
    "                    cur1 += 1\n",
    "                i += 1\n",
    "            while cur1 <= mid:\n",
    "                tmp1[i] = nums[cur1]\n",
    "                tmp2[i] = index[cur1]\n",
    "                cur1 += 1\n",
    "                i += 1\n",
    "            while cur2 <= right:\n",
    "                tmp1[i] = nums[cur2]\n",
    "                tmp2[i] = index[cur2]\n",
    "                cur2 += 1\n",
    "                i += 1\n",
    "            nums[left:right + 1] = tmp1[left:right + 1]\n",
    "            index[left:right + 1] = tmp2[left:right + 1]\n",
    "        \n",
    "        merageSort(0, n - 1)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
